Course Outline HCT423 Design and Analysis of Algorithms

UNIVERSITY OF ZIMBABWE
Course Outline HCT423 Design and Analysis of Algorithms

Instructor: Dr. Nelson Ruwa ([email protected] +263717479886)
Course Description
This course will cover the basic approaches and mindsets for analysing and designing algorithms
and data structures. Topics include the following: Worst and average case analysis. Recurrences
and asymptotics. Efficient algorithms for sorting, searching, and selection. Data structures:
binary search trees, heaps, hash tables. Algorithm design techniques: divide-and-conquer,
dynamic programming, greedy algorithms, amortized analysis, randomization. Algorithms for
fundamental graph problems: minimum-cost spanning tree, connected components, topological
sort, and shortest paths. Possible additional topics: network flow, string searching.
Course Calendar
The Course runs from 15 November 2021 – 10 December 2021 Mondays to Friday
Venue: Online – Join Google Classroom for notifications and lecture links
Time: 9AM – 1PM (Adjustments will be communicated)
Course Objectives
Upon completion of this course, students will be able to do the following:
● Analyze the asymptotic performance of algorithms.
● Write rigorous correctness proofs for algorithms.
● Demonstrate a familiarity with major algorithms and data structures.
● Apply important algorithmic design paradigms and methods of analysis.
● Synthesize efficient algorithms in common engineering design situations.
Course Outcomes
Students who complete the course will have demonstrated the ability to do the following:
● Argue the correctness of algorithms using inductive proofs and invariants.
● Analyze worst-case running times of algorithms using asymptotic analysis.
● Describe the divide-and-conquer paradigm and explain when an algorithmic design
situation calls for it. Recite algorithms that employ this paradigm. Synthesize divide-
and-conquer algorithms. Derive and solve recurrences describing the performance of
divide-and-conquer algorithms.
● Describe the dynamic-programming paradigm and explain when an algorithmic
design situation calls for it. Recite algorithms that employ this paradigm. Synthesize
dynamic-programming algorithms, and analyze them.
● Describe the greedy paradigm and explain when an algorithmic design situation calls
for it. Recite algorithms that employ this paradigm. Synthesize greedy algorithms,
and analyze them.
● Explain the major graph algorithms and their analyses. Employ graphs to model
engineering problems, when appropriate. Synthesize new graph algorithms and
algorithms that employ graph computations as key components, and analyze them.
● Explain the different ways to analyze randomized algorithms (expected running time,
probability of error). Recite algorithms that employ randomization. Explain the
difference between a randomized algorithm and an algorithm with probabilistic
inputs.
● Analyze randomized algorithms. Employ indicator random variables and linearity of
expectation to perform the analyses. Recite analyses of algorithms that employ this
method of analysis.
● Explain what amortized running time is and what it is good for. Describe the different
methods of amortized analysis (aggregate analysis, accounting, potential method).
Perform amortized analysis.
● Explain what competitive analysis is and to which situations it applies. Perform
competitive analysis.
● Compare between different data structures. Pick an appropriate data structure for a
design situation.
● Explain what an approximation algorithm is, and the benefit of using approximation
algorithms. Be familiar with some approximation algorithms, including algorithms
that are PTAS or FPTAS. Analyze the approximation factor of an algorithm.
COURSE CONTENT
1. Introduction to Design and Analysis of Algorithms
● Introduction
● Algorithm
● Need of Algorithm
● Complexity of Algorithm
● Algorithm Design Techniques
2. Asymptotic Analysis
● Asymptotic Analysis
● Analysing Algorithm Control Structure
3. Recurrence
● Recurrence Relation
● Recursion Tree Method
● Master Method
4. Analysis of Sorting
● Bubble Sort
● Selection Sort
● Insertion Sort
5. Divide and Conquer
● Introduction
● Max-Min Problem
● Binary Search
● Merge Sort
● Tower of Hanoi
6. Sorting
● Binary Heap
● Quick Sort
● Stable Sorting
7. Lower bound Theory
● Lower bound Theory
8. Sorting in Linear Time
● Linear Time
● Counting Sort
● Bucket Sort
● Radix Sort
9. Hashing
● Hashing
● Hash Tables
● Hashing Method
● Open Addressing Techniques
● Hash Function
10. Binary Search Trees
● Binary Search
11. Red Black Tree
● Red Black Tree
12. Dynamic Programming
● Dynamic Programming
● Divide & Conquer Method vs Dynamic Programming
● Fibonacci sequence
● Matrix Chain Multiplication
● Matrix Chain Multiplication Example
● Matrix Chain Multiplication Algorithm
● Longest Common Sequence
● Longest Common Sequence Algorithm
● 0/1 Knapsack Problem
● DUTCH NATIONAL FLAG
● Longest Palindrome Subsequence
● Longest Increasing Subsequence
● Longest Common Subsequence
● Tabulation vs Memoization
● How to solve a dynamic programming problem
● Optimal Substructure Property
● Overlapping sub-problems
● Dynamic programming vs Greedy approach
● Regular Expression Matching
● Branch and bound vs backtracking
● Branch and bound
● Longest Repeated Subsequence
● Longest Common Substring
● Shortest Common Supersequence
● Dynamic Programming vs Divide and Conquer
● Maximum Sum Increasing Subsequence
● Wildcard Pattern Matching
● Largest Sum Contiguous Subarray
● Shortest Sum Contiguous Subarray
13. Greedy Algorithm
● Greedy Algorithms
● Activity Selection Problem
● Fractional Knapsack problem
● Huffman Codes
● Algorithm of Huffman Code
● Activity or Task Scheduling Problem
● Travelling Sales Person Problem
● Dynamic Programming vs Greedy Method
14. Backtracking
● Backtracking Introduction
● Recursive Maze Algorithm
● Hamiltonian Circuit Problems
● Subset Sum Problems
● N Queens Problems
15. Minimum Spanning Tree
● MST Introduction
● MST Applications
● Kruskal's Algorithm
● Prim's Algorithm
16. Shortest Path
● Introduction
● Negative Weight Edges
● Representing Shortest Path
● Relaxation
● Dijkstra's Algorithm
● Bellman-Ford Algorithm
● Single Source Shortest Path in a directed Acyclic Graphs
17. All-Pairs Shortest Paths
● Introduction
● Floyd-Warshall Algorithm
● Johnson's Algorithm
18. Maximum Flow
● Flow networks and Flows
● Network Flow Problems
● Ford Fulkerson Algorithm
● Maximum bipartite matching
19. Sorting Networks
● Comparison Network
● Bitonic Sorting Network
● Merging Network
20. Complexity Theory
● Complexity Classes
● Polynomial Time Verification
● NP-Completeness
● Circuit Satisfiability
● 3-CNF Satisfiability
● Clique Problem
● Vertex Cover Problem
● Subset-Sum Problem
21. Approximation Algo
● Introduction
● Vertex Cover
● Travelling Salesman Problem
22. String Matching
● Introduction
● Naive String Matching Algorithm
● Rabin-Karp-Algorithm
● String Matching with Finite Automata
● Knuth-Morris-Pratt Algorithm
● Boyer-Moore Algorithm
REFERENCES
Dasgupta, Sanjoy, Christos Papadimitriou, and Umesh Vazirani. Algorithms. McGraw-Hill,
2006. ISBN: 9780073523408.
Kleinberg, Jon, and Eva Tardos. Algorithm Design. Addison-Wesley, 2005. ISBN:
9780321295354.
Skiena, Steven. The Algorithm Design Manual 3rd Edition. Springer, 2020.
https://www.javatpoint.com/daa-tutorial

Course Outline HCT423 Design and Analysis of Algorithms

Uploaded by

Copyright:

Available Formats

Course Outline HCT423 Design and Analysis of Algorithms

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Course Outline HCT423 Design and Analysis of Algorithms

Uploaded by

Copyright:

Available Formats

UNIVERSITY OF ZIMBABWE

Course Outline HCT423 Design and Analysis of Algorithms

You might also like