A continuation of Data Structures and Algorithms 1 course with an emphasis on design of algorithms. More advanced data structures and algorithms on these data structures together with their analysis will be introduced. Couse topics include: amortized analysis and self-adjusting data structures for trees and priority queues, AVL and Red-Black trees; union-find; efficient algorithms for for data structures including trees, strings, and graphs; sorting and pattern matching algorithms, text processing; dynamic programming, greedy and divide-and-conquer paradigms.
Prerequisite(s)
Discrete Mathematics, Fundamentals of Data Structure and Algorithm
Corequisite(s)
Course Code Course Name…
Special Requisite(s)
To be familiar with a programming language such as C, C++
- Theory
- Designing pseudo codes for given problems
- Designing, writing and runnign the problems with a programming language such as C, C++.
Principle Sources
Ø Anany Levitin, Introduction to the Design and Analysis of Algorithms. Pearson Education, 3rd ed. ISBN: 9780132316811.
Ø Introduction to Algorithms, 3rd Edition (The MIT Press) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
Other Sources
Ø D. S. Malik (2013). C++ Programming: Program Design Including Data Structures, International Edition, 6th Edition (International Edition), Cengage Learning.
Course Schedules
Week
Contents
Learning Methods
1. Week
Course Introduction and overview.
Analysis of Algorithms, Growth of Functions, Asymptotic notation and Divide & Conquer
Theory
2. Week
Sorting and order statistics: Priority queues, quicksort, sorting in linear time, medians, and order statistics.
Theory
3. Week
Binary search trees, augmenting data structures, red-black trees.
Theory and Lab.
4. Week
B-trees; operations on B-trees, searching, insertion, deletion.
Theory and Lab.
5. Week
Introduction to graph theory and representations of graphs.
Theory and Lab.
6. Week
Types of graphs, representation of graphs on computer memories. Examples.
Theory and Lab.
7. Week
Problems that can be solved using graph theory: Graph coloring, shortest path, spanning tree, and etc.
Theory and Lab.
8. Week
Graph coloring: Powel and Welch algorithm. Different types of exampless using graph coloring.
Theory and Lab.
9. Week
Shortest path algorithms and behaivor of Dijkstra's algorithm.
Theory and Lab.
10. Week
Applicaiton of Dijkstra's algorithm on a map.
Theory and Lab.
11. Week
Algorithms of minumum spanning tree. Kruskla's algorithm.
Theory and Lab.
12. Week
To calculate running time and complexity. Big O notation.
Theory and Lab.
13. Week
Compression algorithms and programs.
Theory and Lab.
14. Week
Huffman coding tree and it's sample applications: Characters usage frequencies and Huffman tree. Generating variable-lenght code.
Theory and Lab.
15. Week
Probability theory and it's applications. Time and space frequencies.
Theory and Lab.
16. Week
Grammer decoding algorithms.
Theory and Lab.
17. Week
Review computer Olympic problems.
Theory and Lab.
Assessments
Evaluation tools
Quantity
Weight(%)
Midterm(s)
1
25
Homework / Term Projects / Presentations
3
15
Project(s)
1
20
Attendance
1
5
Final Exam
1
35
Program Outcomes
PO-1
Adequate knowledge in mathematics, science and engineering subjects pertaining to the relevant discipline; ability to use theoretical and applied information in these areas to model and solve engineering problems.
PO-2
Ability to identify, formulate, and solve complex engineering problems; ability to select and apply proper analysis and modelling methods for this purpose.
PO-3
Ability to design a complex system, process, device or product under realistic constraints and conditions, in such a way so as to meet the desired result; ability to apply modern design methods for this purpose. (Realistic constraints and conditions may include factors such as economic and environmental issues, sustainability, manufacturability, ethics, health, safety issues, and social and political issues according to the nature of the design.)
PO-4
Ability to devise, select, and use modern techniques and tools needed for engineering practice; ability to employ information technologies effectively.
PO-5
Ability to design and conduct experiments, gather data, analyse and interpret results for investigating engineering problems.
PO-6
Ability to work efficiently in intra-disciplinary and multi-disciplinary teams; ability to work individually.
PO-7
Ability to communicate effectively, both orally and in writing; knowledge of a minimum of one foreign language.
PO-8
Recognition of the need for lifelong learning; ability to access information, to follow developments in science and technology, and to continue to educate him/herself.
PO-9
Awareness of professional and ethical responsibility.
PO-10
Information about business life practices such as project management, risk management, and change management; awareness of entrepreneurship, innovation, and sustainable development.
PO-11
Knowledge about contemporary issues and the global and societal effects of engineering practices on health, environment, and safety; awareness of the legal consequences of engineering solutions.
Learning Outcomes
LO-1
Describe how to implement priority queues, hash tables and search trees.
LO-2
Selecting an optimum algorithm for given problems
LO-3
Graph theory and related problems such as shortest path, spanning tree, graph coloring, and etc.
LO-4
Usage skill data models in engineering applications
LO-5
Describe how to implement priority queues, hash tables and search trees.
