Lecture 3: Analysis of Algorithms I

Majid Khonji

201

1

www.avlab.io

Khalifa University

ROBO

Course Structure

Module 1: Algorithm Fundamentals

• Today:
• Lists (Arrays) and LinkedLists
• Analysis of algorithms part 1 (out of 4)

Module 2: Path Planning in Discrete Spaces

Module 3: Path Planning in Continuous Spaces

2

ku.ac.ae

Lists (and Arrays)

• Python list Revision
• Under the Hood

3

Recap: Lists

• To store collections of data, Python has 4 built-in data types: lists, tuples, sets, and dictionaries
• Many items can be stored in a single variable using lists
• A list consist of items separated by commas and enclosed within square brackets

4

Example:

mylist = ["cup",20,2.3,"football",True]

A list can contain different data types – string, integer, float, Boolean, even other lists etc.

ku.ac.ae

Lists

Examples:

odd = [1,3,5,7,9]

year = [2020,2021,2022,2023,2024]

subjects = ['Physics','Chemistry','English','Biology']

mix = [1,'Abu Dhabi',5.6,1e6,'car’]

listoflist1 = [[1,2,3],[4,5,6],3]

listoflist2 = [[1,2,3],[4,5,6],[3,[8,9,1]]]

5

ku.ac.ae

Lists

1. Ordered
2. Changeable: after a list has been made, it is possible to edit, add, and remove items from it
3. Can have items with the same value

6

mylist = ["cup",20,2.3,"football",True,"cup"]

ku.ac.ae

List Access

• The values stored in a list are accessed using indexes.
• If n is the total number of elements in the list, then the index of the first element is 0 while the index of the last element is n-1

7

mylist = ["cup",20,2.3,"football",True,"cup"]

Output :

cup 20 2.3 football

0

1

2

3

4

5

print(mylist[0],mylist[1],mylist[2],mylist[3])

ku.ac.ae

List Access

• Negative Indexing : Negative indexing means start from the end. -1 refers to the last item, -2 refers to the second last item, and so on…

​

8

mylist = ["cup",20,2.3,"football",True,"cup"]

�print(mylist[-1],mylist[-2],mylist[-3])

Output :

cup True football

-6

-5

-4

-3

-2

-1

ku.ac.ae

List Access

• The range of indexes can be specified by specifying where the range begins and ends.
• To access values in lists, square brackets are used to slice along with the index(es) to get value(s) stored at that index(es) – Slicing

​

​

​

9

mylist = ["cup",20,2.3,"football",True,"cup"]

�print(mylist[2:4])

Output :

[2.3, 'football']

mylist = ["cup",20,2.3,"football",True,"cup"]

�print(mylist[-4:-1])

Output :

[2.3, 'football', True]

ku.ac.ae

List Access

The range of indexes can be specified without beginning and end

​

​

​

​

10

mylist = ["cup",20,2.3,"football",True,"cup"]

�print(mylist[:4])

Output :

['cup', 20, 2.3, 'football']

mylist = ["cup",20,2.3,"football",True,"cup"]

�print(mylist[2:])

Output :

[2.3, 'football', True, 'cup']

ku.ac.ae

List Access

• In the slice operation, you can specify an optional third argument as the stride, which refers to the number of items to move forward after the first item is retrieved from the list.
• By default, the value of stride is 1

11

Output :

[20, 2.3, 'football', True, 'cup']

[20, 2.3, 'football', True, 'cup']

[20, 'football', 'cup']

mylist = ["cup",20,2.3,"football",True,"cup"]

print(mylist[1:6]) # default stride=1

print(mylist[1:6:1]) # stride=1

print(mylist[1:6:2]) # stride=2, skips every second character

ku.ac.ae

List Access

12

Output :

['cup', 2.3, True]

[20]

['cup', 2.3, True]

['cup', 'football']

mylist = ["cup",20,2.3,"football",True,"cup"]

print(mylist[0:10:2]) # stride=2, skips every second character

print(mylist[1:6:5]) # stride=5, skips every fifth character

print(mylist[::2]) # stride=2, no beginning or end

print(mylist[-6:-1:3]) # stride=3, negative indexing

What is the output of print(mylist[::-1])?

ku.ac.ae

Under the Hood

• We will use list data structure
• The same ideas hold for Arrays
• You will use arrays in ROBO 202 (with numpy lib)

13

Example: Scoreboard

• Keep track of players and their best scores in a list
• We keep only the top (capacity=5) players in the list, in descending order

14

board = [("Ali", 90), ("Sara", 85), ("Hassan", 80), None, None]

capacity = 5

ku.ac.ae

Adding an Entry

• To add an entry e into list board at index i, we need to make room for it.

15

by shifting forward the n − i entries board[i], …, board[n − 1]

ku.ac.ae

Adding an Entry - Code

16

board = [("Ali", 90), ("Sara", 85), ("Hassan", 80), None, None]

capacity = 5

def add_entry(board, entry, capacity):

name, score = entry

if board[-1] is not None: # Check if the board is full (last slot not empty)

print("Board full!")

return board

# Find correct position (descending order by score)

i = 0

while i < len(board) and board[i] is not None and board[i][1] >= score:

i += 1

# Shift elements to the right

j = len(board) - 1

while j > i:

board[j] = board[j - 1]

j -= 1

board[i] = entry # Insert new entry

return board

​

ku.ac.ae

Removing an Entry

• To remove the entry e at index i, we need to fill the hole left by e by shifting backward the n − i − 1 elements board[i + 1], …, board[n − 1]

17

e

board

ku.ac.ae

Remove Entry at location i

18

​

# Pop method does the same thing under the hood

def remove_entry(board, i):

if 0 <= i < len(board):

board.pop(i)

return board

​

def remove_entry(board, i):

n = len(board)

if 0 <= i < n:

removed = board[i]

# Shift all elements left, overwriting index i

for j in range(i, n-1):

board[j] = board[j+1]

# Trim the duplicate last element

del board[-1]

print("Removed:", removed)

else:

print("Invalid index")

return board

Driver Code

​

19

print("Initial board:", board)

​

# Add new players

board = add_entry(board, ("Fatima", 88), capacity)

print("After adding Fatima:", board)

​

board = add_entry(board, ("Omar", 95), capacity)

print("After adding Omar:", board)

​

# Try to add beyond capacity

board = add_entry(board, ("Laila", 70), capacity)

board = add_entry(board, ("Noura", 60), capacity) # should fill

board = add_entry(board, ("Yousef", 75), capacity) # should reject

​

# Remove a player (index 2 for example)

board = remove_entry(board, 2)

print("After removing index 2:", board)

Initial board: [('Ali', 90), ('Sara', 85), ('Hassan', 80), None, None]

After adding Fatima: [('Ali', 90), ('Fatima', 88), ('Sara', 85), ('Hassan', 80)]

After adding Omar: [('Omar', 95), ('Ali', 90), ('Sara', 85), ('Fatima', 88), ('Hassan', 80)]

Board full! Cannot add: ('Noura', 60)

Removed: ('Sara', 85)

After removing index 2: [('Omar', 95), ('Ali', 90), ('Fatima', 88), ('Hassan', 80)]

​

Singly Linked List

Not Python List

20

Singly Linked List

• A singly linked list is a concrete data structure consisting of a sequence of nodes, starting from a head pointer
• Each node stores
• element
• link to the next node

21

next

element

node

A

B

C

D

∅

head

ku.ac.ae

Inserting at the Head

• Allocate new node
• Insert new element
• Have new node point to old head
• Update head to point to new node

​

22

ku.ac.ae

Inserting at the Tail

• Allocate a new node
• Insert new element
• Have new node point to null
• Have old last node point to new node
• Update tail to point to new node

​

23

ku.ac.ae

Implementation Notes

Recap: Dictionaries

• A dictionary stores data as key–value pairs
• Unordered, changeable, no duplicate keys
• Very fast lookups
• Syntax: { key: value, ... }

24

student = {

"name": "Ali",

"age": 20,

"major": "CS"

}

ku.ac.ae

Recap: Dictionary Access & Manipulation

• Access a value using its key

​

​

• If key doesn’t exist → error (or use .get() safely)

25

print(student["name"]) # Ali

print(student.get("age")) # 20

student["gpa"] = 3.8 # add

student["age"] = 21 # update

ku.ac.ae

Linked List Implementation

• We define a node as a dictionary:

​

• We use two variables, head and tail reference to the corresponding nodes in the list
• We can get a “list” by simply adding a node to “next” of previous node

26

Node = {"data": data, "next": next}

NodeB = {"data": "B", "next": None}

NodeA = {"data": "A", "next": NodeB}

ku.ac.ae

Display LinkedList

27

def display(head):

curr = head

while curr is not None:

print(curr["data"])

curr = curr["next"]

NodeB = {"data": "B", "next": None}

NodeA = {"data": "A", "next": NodeB}

display(head) # List: A, B

ku.ac.ae

Linked List Insert Implementation using Dictionary

28

def insert_at_head(head, tail, data):

new_node = {"data": data, "next": head}

if head is None: # empty list

tail = new_node

head = new_node

return head, tail

​

def insert_at_tail(head, tail, data):

new_node = {"data": data, "next": None}

if tail is None: # empty list

head = new_node

tail = new_node

else:

tail["next"] = new_node

tail = new_node

return head, tail

​

head, tail = insert_at_head(head, tail, "C")

head, tail = insert_at_head(head, tail, "B")

head, tail = insert_at_head(head, tail, "A")

display(head) # A -> B -> C

​

head, tail = insert_at_tail(head, tail, "D")

display(head) # A -> B -> C -> D

​

head, tail = remove_at_head(head, tail)

display(head) # B -> C -> D

​

ku.ac.ae

Removing at the Head

• Update head to point to next node in the list
• Allow garbage collector to reclaim the former first node

29

ku.ac.ae

Remove at Head Code

30

def remove_at_head(head, tail):

if head is None:

print("List empty")

return None, None

removed = head["data"]

head = head["next"]

if head is None: # list became empty

tail = None

print("Removed at head:", removed)

return head, tail

Removing at the Tail

• Removing at the tail of a singly linked list is not efficient! Why?
• There is no constant-time way to update the tail to point to the previous node

31

ku.ac.ae

Remove at Tail Code (will come back to it later)

32

def remove_at_tail(head, tail):

if head is None:

print("List empty")

return None, None

if head["next"] is None: # only one node

removed = head["data"]

print("Removed at tail:", removed)

return None, None

# traverse to second-last node

curr = head

while curr["next"]["next"] is not None:

curr = curr["next"]

removed = curr["next"]["data"]

curr["next"] = None

tail = curr

print("Removed at tail:", removed)

return head, tail

ku.ac.ae

Analysis of Algorithms I

33

Algorithm

Input

Output

Running Time

• Most algorithms transform input objects into output objects.
• The running time of an algorithm typically grows with the input size.
• Average case time is often difficult to determine.
• We focus on the worst-case running time.
• Easier to analyze
• Crucial to applications such as games, finance and robotics

34

ku.ac.ae

Experimental Studies Approach

• One approach to test an Alg.:
• Write a program implementing the algorithm
• Run the program with inputs of varying size and composition, noting the time needed:
• Plot the results

​

35

import time

start_time = time.perf_counter()

# --- run the algorithm here ---

end_time = time.perf_counter()

elapsed = (end_time - start_time) * 1000

print("Elapsed time:", elapsed, "milliseconds")

ku.ac.ae

Limitations of Experiments

• It is necessary to implement the algorithm, which may be difficult
• Results may not be indicative of the running time on other inputs not included in the experiment.
• In order to compare two algorithms, the same hardware and software environments must be used

36

ku.ac.ae

Theoretical Analysis

• Characterizes running time as a function of the input size, n
• Takes into account all possible inputs
• Allows us to evaluate the speed of an algorithm independent of the hardware/software environment
• Uses a high-level description of the algorithm instead of an implementation

​

37

ku.ac.ae

Pseudocode

• High-level description of an algorithm
• More structured than English prose
• Less detailed than a program
• Preferred notation for describing algorithms
• Hides program design issues

38

ku.ac.ae

Pseudocode Details

• Control flow
• if … then … [else …]
• while … do …
• repeat … until …
• for … do …
• Indentation replaces braces
• Method declaration

Algorithm method (arg [, arg…])

Input …

Output …

• Method call

method (arg [, arg…])

• Return value

return expression

• Expressions:

← Assignment�

= Equality testing�

n² Superscripts and other mathematical formatting allowed

​

39

Seven Important Functions

• Seven functions that often appear in algorithm analysis:
• Constant ≈ 1
• Logarithmic ≈ log n
• Linear ≈ n
• N-Log-N ≈ n log n
• Quadratic ≈ n²
• Cubic ≈ n³
• Exponential ≈ 2ⁿ

40

ku.ac.ae

The Seven Functions

41

g(n) = n lg n

Slide by Matt Stallmann included with permission

Side by side

ku.ac.ae

Primitive Operations

• Basic computations performed by an algorithm
• Identifiable in pseudocode
• Largely independent from the programming language
• Exact definition not important (we will see why later)
• Assumed to take a constant amount of time in the RAM model

• Examples:
• Evaluating an expression
• Assigning a value to a variable
• Indexing into an array
• Calling a method
• Returning from a method

42

The Random Access Machine (RAM) Model

A RAM consists of

• A CPU
• An potentially unbounded bank of memory cells, each of which can hold an arbitrary number or character
• Memory cells are numbered and accessing any cell in memory takes unit time

​

43

ku.ac.ae

Counting Primitive Operations

• By inspecting the pseudocode, we can determine the maximum number of primitive operations executed by an algorithm, as a function of the input size. For example:

44

# Returns the maximum value of a nonempty list of numbers.

def array_max(data):

n = len(data) # 3: 2 ops (len + assign)

current_max = data[0] # 4: 2 ops (index + assign)

j = 1 # 5: 1 op (init)

while j < n: # 5: n comps

if data[j] > current_max: # 6: 2(n-1) ops

current_max = data[j] # 7: 0 to 2(n-1) ops

j = j + 1 # 5: 2(n-1) increments

return current_max # 8: 1 op

​

ku.ac.ae

Estimating Running Time

• Algorithm arrayMax executes
• 7n primitive operations in the worst case
• 5n + 2 in the best case (Line 7: 0 to 2(n-1) ops)
• Define:

a = Time taken by the fastest primitive operation

b = Time taken by the slowest primitive operation

• Let T(n) be worst-case time of arrayMax. Then� a (5n + 2) ≤ T(n) ≤ b(7n)
• Hence, the running time T(n) is bounded by two linear functions

45

ku.ac.ae

Growth Rate of Running Time

• Changing the hardware/software environment
• Affects T(n) by a constant factor, but
• Does not alter the growth rate of T(n)

​

• The linear growth rate of the running time T(n) is an intrinsic property of algorithm arrayMax

46

ku.ac.ae