COMP1081 Algorithms: Introduction and Pseudocode

• The module is titled COMP1081 - Algorithms and Data Structures.
• The lecture uses Poll Everywhere for anonymous Q&A.
• The Poll Everywhere presentation can be joined via the app (eamonn) or online.
• No sign-up is required for Poll Everywhere.

Topic 1: Introduction and Pseudocode

• The lecture slides are by Eamonn Bell.
• Eamonn Bell can be contacted via [email protected]

Algorithms and Data Structures

• A network, consisting of nodes with links, requires the cheapest possible way of connecting all nodes.
• A solution involves finding a minimum cost of connections.
• An algorithm should be describable no matter how many millions of nodes there are.
• The cheapest edge that makes new connections is repeatedly picked and added to the solution.
• An algorithm presented to solve a problem needs to be correct and practical.
• The way the network data is stored on a computer can affect the efficiency of an algorithm.

Algorithms

• An algorithm is a method or process to solve a problem.
• An algorithm must have correctness, concrete unambiguous steps, a finite number of steps, and termination.

Data Structures

• A data structure is a way of storing and organizing data in a computer for efficient use.
• Data structures and algorithms are studied to solve problems efficiently, making the best use of space and time.
• The choice of data structure or algorithm can significantly impact program running time.
• The module covers commonly used data structures, algorithmic techniques, and measuring the cost of data structures/algorithms.
• Analysing Algorithms (asymptotic classes), Basic data structures, Binary search, Graph algorithms, Introduction & pseudocode, Recursive algorithms, and Sorting are all module content.
• The module consists of 40 one-hour lectures and 19 one-hour practicals.
• The lecturers are Eamonn Bell, Thomas Erlebach (module coordinator), Anish Jindal, and Amitabh Trehan.
• The course text is Data Structures and Algorithms in Python (or Java) by Goodrich et al.
• Course materials are available on Learn Ultra.

Assessment

• There is an assignment due 23rd January 2025; information is available on Sharepoint > Department of Computer Science Undergraduate Community.
• There will be an end of year exam.
• Eamonn Bell Office hours are in person at MCS 2105, 10 a.m. - 11 a.m. on Thursdays during Part I, or by email for an appointment otherwise.
• The module is one of six modules and might consume about six hours of time each week.
• Three hours are for lectures (2 attending, 1 reviewing).
• Three hours are for practicals (preparing, 2 attending, and reviewing).
• Practical begins on the week starting 14th October 2025, where attendance is taken.
• Writing pseudocode, implementing (in Python), and working on problem sets gives practical knowledge.
• MEQs (Module Evaluation Questionnaires) are filled in by students for ADS each year around the end of the 2nd term.
• Additional guidance for Python implementation has been added in Part 1 practicals for 24/25.
• Only the programming concepts covered in CT (Concept Training, Computer Theory) are required to solve the coursework.
• Slides for Part 2 will be provided for each topic separately, and Part 4 has been revised.

RAM model of computation

• A Random Access Machine (RAM) is a highly simplified model of computation to determine the efficiency of an algorithm.
• RAM Memory consists of an infinite array
• Instructions are executed sequentially one at a time in the RAM model.
• All instructions take unit time.
• Running time is the number of instructions executed.

Pseudocode

• General pseudocode is used to describe algorithms, not a specific programming language.
• Pseudocode has no strict rules, but rather a typical framework.
• Variables will often need to be used
• Basic types include integer, float, char(acter), and string.
• "Important" variables should be explicitly declared regarding their type of storage.
• Values are assigned to variables.
• Multiple variables can be declared in one go, i.e. integer x=0, y=2, z=3.
• Arithmetic operations utilize parentheses for grouping, and +-*/ for add, subtract, multiply, and divide.
• Logical operations consist of AND, OR, and NOT.
• The keyword "print" is used for printing outputs.
• Concatenation uses a comma, but elsewhere may use '+'.

If-then-else

Simple if-then

if condition then
    statement
    statement
end if

• Conditions often involve comparisons.
• Comparisons: < > <= (≤) >= (≥) == (=) != (≠)
• It's good pseudocode style to visually indent the "body" of a conditional statement.

if x ≠ 0 then
    z = y/x
end if

if x ≠ 0 then
    z = y/x
else
    print "division by zero error"
end if

• Nested conditionals can be constructed, i.e.

if condition then
    statement
    if condition then
      statement
      statement
    else
      statement
    end if
else
    if condition then
      statement
    end if
end if

For loop

• To iterate some numerical variable through some range you can use the for loop

for variable = lower to upper do
  body (will often depend on variable)
end for

• "Body" is simply a sequence of statements (and may contain If-Then-Elses, other loops, whatever).

integer sum = 0
for i = 1 to 10 do
  sum = sum + i
end for
print sum

• To iterate over a given base set

for value in {value1, value2,...} do
  body (will often depend on value)
end for

• Example

integer sum = 0
for prime in { 2, 3, 5, 7 } do
  sum = sum+ prime
end for

• Iterate through a range and increment by a stated value

for i = 0 to 9; i += 2 do
 print i
end for

• Clearer way to write it

for i = 9 to 0; i += −1 do
  print i
end for

While loop

• To do something while some condition is true

while condition do
  body
end while

• Example

sum = 0
x = 1
while x ≤ 10 do
  sum = sum +x
  x=x+1
end while
print "sum of numbers between 1 and 10 is", sum

• for increments loop-variable automatically; while doesn't

for i = 1 to 10 do
  print i
end for

i = 1
while i ≤ 10 do
  print i      ← need to increment i by hand
  i=i+1
end while

Everything can be nested: Question 9

for x = 1 to 4 do
  for y = 1 to 4 do
    go to coordinate (x, y)
    plot red circle of diameter 0.1
  end for
end for

• Swapping the first two lines can also be nested.