Evaluation:
Assignments 50%, quizzes 20%, final exam 30%
Copying is fatal
Teaching assistant: Rebhu Johymalyo Josh
Submit all assignment solutions via Moodle.
Assignment 1, 24 August 2014, due 31 August, 2014.
Assignment 2, 7 September 2014, due 14 September, 2014.
Assignment 3, 29 September 2014, due 8 October, 2014.
Assignment 4, 7 October 2014, due 13 October, 2014.
Assignment 5, 19 October 2014, due 25 October, 2014.
Assignment 6, 26 October 2014, due 4 November, 2014.
Assignment 7, 8 November 2014, due 15 November, 2014.
Assignment 8, 19 November 2014, due 29 November, 2014.
The stuff I write during class, to jog your memory.
Introduction to programming, algorithms, data structures using gcd as running example
gcd continued: functions, termination, efficiency, introduction to Python
Python: numeric and boolean values, operations, expressions; strings, lists; Python memory model—names and values, mutable and immutable
Strings and lists: slices, mutable vs immutable; control flow: assignments, conditionals, loops
gcd in Python; breaking out of a loop; implicit boolean values; tuples
Running Python programs; tuples; more on lists and mutability; inductive function definitions—numeric and structural induction
Inductive function definitions; sorting—selection sort, insertion sort
Sorting in place—selection sort, insertion sort; basic analysis of algorithmic complexity—inputs size, asymptotic complexity, O() notation
Asymptotic complexity; arrays vs lists; merge sort (divide and conquer); stability of sorting algorithms
Quicksort—recursive, in-place, worst case vs average case
Python dictionaries; function definitions—optional/default values of parameters; passing functions as arguments
Order of evaluation in conditional expressions; function definitions— generalization of assignment of values to names, dynamic (re)assignment of function definitions, passing functions as arguments; operating on lists—map and filter, list comprehension
Exception handling; basic input/output in Python
Input/output using files; string functions—strip(), split()
Data structures: queues, stacks; priority queue—list implementation, 2D array; binary tree basics
Heaps: insert, delete_max(), heapify
Heaps: heapify, heapsort; abstract data types—separating interface and implementation
Abstract datatypes and object-oriented programming: basics of classes and objects in Python
Backtracking: N queens
Backtracking: recording all solutions; Python scope: global and nonlocal names, nested functions; Generating all permutations of 1..N
"Linked" lists in Python: class Node, append
"Linked" lists in Python: delete, insert; Search trees
Tree traversals; Search trees: find, insert, delete
Search trees in Python; Height-balance (introduction)
Height-balanced search trees
Efficient evaluation of recursive definitions: memoization, dynamic programming (examples–fibonacci, grid paths)
Efficient evaluation of recursive definitions: memoization, dynamic programming–fibonacci, grid paths, longest common subsequence
Dynamic programming: longest common subsequence, matrix multiplication