In this course, we will study the design and analysis of efficient algorithms. The focus will be on fundamental design techniques such as greedy approaches, divide and conquer, dynamic programming, network flow, and randomized algorithms. We will study measuring program performance using asymptotic notation.

The principle focus of the lectures will be theoretical. In addition to the lectures and their associated homework assignments, there will be a number of programming assignments, in which you will be required to implement algorithms.

Email:junaid.siddiqui@lums.edu.pk
Office Hours:

Monday 1-2pm, ENS 112-B

Razieh Nokhbeh Zaeem, TA
Email:nokhbeh@gmail.com
Office Hours:

Monday 4-6pm, ENS 122

Xi (James) Zheng, TA
Email:jameszhengxi1979@gmail.com
Office Hours:

Wednesday 2-4pm, ENS 122

Course Information

Class meetings

MWF 11:30am–12:45pm, ENS 116

Pre-requisites

Targeted to undergraduate students who have taken a programming course and are comfortable writing code in some programming language.

Required text

[ISBN/0321295358]

Optional text

[ISBN/0262033844]

Grading

24%Homework assignments (8 assignments)
16%Programming assignments (4 assignments)
40%Midterm Examinations
20%Final Examination

Tentative Schedule

#DateTopicReadings
Topic 1: Foundations

Introduction, Administrivia

Stable Matching

Stable matching analysis and implementation

Asymptotic growth

Topic 1: Graphs

Basic concepts and traversal

Directed graphs

Exam I - 10% - CPE 2.208

Topic 1: Greedy Algorithms

Interval scheduling

Shortest path algorithm

Minimum spanning trees

Implementing Kruskal’s algorithm

Topic 1: Divide and Conquer

Mergesort

Recurrence relations

Integer multiplication

Fast fourier transform

Exam II - 15% - CPE 2.208

Topic 1: Dynamic Programming

Weighted interval scheduling

Knapsack

Sequence alignment

Shortest Paths

Topic 1: Network Flow

Maximum-flow problem

Flows and Cuts

Bipartite matching

Exam III - 15% - CPE 2.208

Topic 1: Revision

Revision

Revision

Revision

Topic 1: NP-Completeness

Reductions

Certifications

Revision

2013/8/17

Final Version 1 Version 2 Version 3 - 20% - 9AM-12PM