Institute of Business Administration

CSE 317: Design and Analysis of Algorithms

(Tentative Course Outline and Syllabus)

Spring 2023
Institute of Business Administration
School of Mathematics and Computer Science

CSE 317: Design and Analysis of Algorithms

“An algorithm must be seen to be believed.”

– Donald Ervin Knuth

1 Logistics

1.1 Teaching Assistants

TBA

1.2 Sections Information

Sections 1 & 2 Section 3 Section 4

(Mega section)
Days: Mon. & Wed. Mon. & Wed. Mon. & Wed.
Time: 10:00am-11:15am 8:30am-9:45am 8:30am-9:45am
Space: Event-hall MAC-8 MCC-11
Instructor: Shahid Hussain Imran Rauf Twaha Meenai
Email: shahidhussain irauf –
@iba.edu.pk
Phone: 3044 – –
Office: Tabba, North Wing 204 Tabba, North Wing 206 –
Office hours: TBA TBA –
LMS: TBA

2 Course Objectives

This is a fundamental course on Algorithms in Computer Science. The main goal of the course
is to develop tools and techniques that aid in designing correct and efficient algorithms for
computational problems and analyzing their correctness and running time. We will study pow-
erful design techniques, such as dynamic programming and randomization, and useful analytical
tools, such as recurrence relations and average case analysis. The algorithms under study are
either quite useful, instructive, beautiful or any combination thereof. After taking this course,
the student will be conversant in the language of algorithms, which is a chief component of
technical interviews and software related jobs.

2
 3 Program Learning Outcomes/Graduate Attributes

Graduate attributes (program learning outcomes - PLO’s) taken from https://www.seoulaccord.

org/document.php?id=79.

PLO-1. Academic Education

[Educational depth and breadth]
Completion of an accredited program of study designed to prepare graduates as computing
professionals

PLO-2. Knowledge for Solving Computing Problems

[Breadth and depth of education and type of knowledge, both theoretical and practical]
Apply knowledge of computing fundamentals, knowledge of a computing specialization,
and mathematics, science, and domain knowledge appropriate for the computing spe-
cialization to the abstraction and conceptualization of computing models from defined
problems and requirements

PLO-3. Problem Analysis

[Complexity of analysis]
Identify, formulate, research literature, and solve complex computing problems reaching
substantiated conclusions using fundamental principles of mathematics, computing sci-
ences, and relevant domain disciplines

PLO-4. Design / Development of Solutions

[Breadth and uniqueness of computing problems, i.e., the extent to which problems are
original and to which solutions have previously been identified or codified]
Design and evaluate solutions for complex computing problems, and design and evaluate
systems, components, or processes that meet specified needs with appropriate considera-
tion for public health and safety, cultural, societal, and environmental considerations

PLO-5. Modern Tool Usage

[Level and appropriateness of the tool to the type of activities performed]
Create, select, adapt and apply appropriate techniques, resources, and modern computing
tools to complex computing activities, with an understanding of the limitations

PLO-6. Individual and Team Work

[Role in, and diversity of, the team]
Function effectively as an individual and as a member or leader in diverse teams and in
multi-disciplinary settings

PLO-7. Communication
[Level of communication according to type of activities performed]
Communicate effectively with the computing community and with society at large about
complex computing activities by being able to comprehend and write effective reports,
design documentation, make effective presentations, and give and understand clear in-
structions

3
 PLO-8. Computing Professionalism and Society
[No differentiation in this characteristic except level of practice]
Understand and assess societal, health, safety, legal, and cultural issues within local and
global contexts, and the consequential responsibilities relevant to professional computing
practice

PLO-9. Ethics
[No differentiation in this characteristic except level of practice]
Understand and commit to professional ethics, responsibilities, and norms of professional
computing practice

PLO-10. Life-long Learning

[No differentiation in this characteristic except level of practice]
Recognize the need, and have the ability, to engage in independent learning for continual
development as a computing professional

4 Course Learning Outcomes

The cognition levels are based on Bloom’s revised taxonomy.1

Course Learning Outcome
CLO Description Cognition
CLO-1 Apply common algorithmic techniques to standard computational prob- Cog-3
lems
CLO-2 Analyze computational complexity of common/standard algorithms Cog-4
CLO-3 Design new algorithms for different computational problems Cog-5
CLO-4 Construct proofs of correctness and time complexity of various algo- Cog-6
rithms

4.1 CLO’s to PLO’s Mapping

PLO-2 PLO-3 PLO-4 PLO-10

CLO-1 ✓
CLO-2 ✓
CLO-3 ✓
CLO-4 ✓

5 Format and Procedures:

The LMS site will be used to share the syllabus, give out assignments, and to share other course
resources.
1
Anderson, Lorin W.; Krathwohl, David R., eds. (2001). A taxonomy for learning, teaching, and assessing:
A revision of Bloom’s taxonomy of educational objectives. Allyn and Bacon

4
The University’s standard policies on attendance, inclusivity, office hours, and academic in-
tegrity apply in this course. These are described in later sections below.

6 Course Requirements
• Class participation policy: Background reading for next session and active participation
in class discussions.

• Course readings will be made available online through the course website and LMS as
classes progress. The following are good references for the material that will be covered.

– Algorithms, by Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani.

– Data Structures and Algorithms in Python, by Michael Goodrich, Roberto Tamas-
sia, and Michael Goldwasser.

• Supplemental reading:

– Introduction to algorithms, by Thomas Cormen, Charles Leiserson, Ronald Rivest

and Clifford Stein.
– Introduction to Analysis of Algorithms, by Robert Sedgewick and Philippe Fla-
jolet.

7 Additional Resource Readings

• The Art of Computer Programming. by Donald Knuth.

• Discrete mathematics and its applications, by Kenneth Rosen.

8 Grading Procedures

Grades will be computed as follows.

Tentative
Problem sets 20%
Weekly quizzes 20%
Midterm 25%
Final 35%

We expect participation and engagement from all students and therefore will be flexible for
deadlines but we will expect that students will generally follow the deadlines.
All quizzes will be in-person and on-campus. Midterm and final exam will follow the University’s
policy and will be scheduled by appropriate offices, separately.

9 Late Work and Makeup Policy

No late solutions will be accepted and no make-up for exams or any of the quizzes will be given.
If you have a valid medical excuse (for any of the quizzes, problem sets, midterm exam, etc.),

5
the percentage of your grade corresponding to the missed work will be shifted to the final exam.
Valid excuses require supporting documentation from a doctor.

10 Attendance Policy

IBA attendance policy applies.

11 Academic Integrity

Each student in this course is expected to abide by the IBA Code of Conduct. Scholastic
dishonesty shall be considered a serious violation of these rules and regulations and is subject
to strict disciplinary action as prescribed by IBA regulations and policies. Scholastic dishonesty
includes, but is not limited to, cheating on exams, plagiarism on assignments, and collusion.
Kindly refer to https://examination.iba.edu.pk/CheatingPlagiarism.php for more de-
tails.

• PLAGIARISM: Plagiarism is the act of taking the work created by another person
or entity and presenting it as ones own for the purpose of personal gain or of obtaining
academic credit. Plagiarism includes the submission of or incorporation of the work of
others without acknowledging its provenance or giving due credit according to established
academic practices. This includes the submission of material that has been appropriated,
bought, received as a gift, downloaded, or obtained by any other means. Students must
not, unless they have been granted permission from all faculty members concerned, submit
the same assignment or project for academic credit for different courses.

• CHEATING: The term cheating shall refer to the use of or obtaining of unauthorized
in- formation in order to obtain personal benefit or academic credit.

• COLLUSION: Collusion is the act of providing unauthorized assistance to one or more

person or of not taking the appropriate precautions against doing so.
Any student violating academic integrity a second time in this course will receive a failing
grade for the course, and additional disciplinary sanctions may be administered.

• SHARING CREDENTIALS: It has been observed that some students share their
credentials (log in id’s and passwords) of LMS, portal, email, etc., with with other students.
These credentials are private and confidential and not to be shared with anyone. Any
violation will be considered as aiding in plagiarism/collusion/cheating and appropriate
action might be taken against such students.

12 Office hours

Office hours will be scheduled, circulated, and posted soon. During these hours the course
instructors will be available to answer questions or provide additional help.

13 Tentavie list of topics

1. Oh-notations and mathematical preliminaries

6
 2. Sorting and searching

3. Recursion and induction

4. Divide and conquer algorithms

5. Dynamic programming

6. Graphs algorithms

7. Greedy algorithms

8. Randomized algorithms

9. String matching algorithms

10. Computational complexity and hardness results

11. Algorithms to cope hardness

12. Introduction to parallel algorithms/computation

7
14 Weekly breakdown of classes

Introduction
Week 1: Lecture 1 16-Jan-23 Introduction, course syllabus
Lecture 2 18-Jan-23 Basics of oh-notations
Search and Sorting
Week 2: Lecture 3 23-Jan-23 Linear search, binary search
Lecture 4 25-Jan-23 Selection sort, insertion sort
Recursion and Induction
Week 3: Lecture 5 30-Jan-23 Integer exponentiation, polynomial evaluation
Lecture 6 01-Feb-23 Generating permutations, finding major. element
Divide and Conquer Algorithms
Week 4: Lecture 7 06-Feb-23 Merge sort, master theorem
Lecture 8 08-Feb-23 Recurrences
Week 5: Lecture 9 13-Feb-23 Integer multiplication
Lecture 10 15-Feb-23 Maximum subarray sum
Dynamic Programming
Week 6: Lecture 11 20-Feb-23 Matrix-chain multiplication
Lecture 12 22-Feb-23 Longest common subsequence
Week 7: Lecture 13 27-Feb-23 Shortest paths
Lecture 14 15-Mar-23 Edit distance, knapsack problem
Greedy Algorithms
Week 8: Lecture 15 20-Mar-23 Single source shortest path: Dijkstra’s algo.
Lecture 16 22-Mar-23 Minimum spanning trees: Prim’s algo.
Randomized Algorithms
Week 9: Lecture 17 27-Mar-23 Introduction to randomized algorithms
Lecture 18 29-Mar-23 Basic probability theory
Week 10: Lecture 19 03-Apr-23 Quick select, quick sort
Lecture 20 05-Apr-23 Pattern matching, random sampling
String Matching Algorithms
Week 11: Lecture 21 10-Apr-23 Rabin-Karp and naive algos.
Lecture 22 12-Apr-23 Knuth-Morris-Pratt and Beyer-Moore algos.
Computational Complexity
Week 12: Lecture 23 17-Apr-23 Class P, class NP
Lecture 24 19-Apr-23 NP-hard and NP-complete problems
Approximation Algorithms
Week 13: Lecture 25 24-Apr-23 Approximation algorithms for hard problems
Lecture 26 26-Apr-23 Approximation algorithms for hard problems
Parallel Algorithms/Computation
Week 14: Lecture 27 01-May-23 Introduction to parallel algorithms
Lecture 28 03-May-23 Models of parallel computation
Revision
Week 15: Lecture 29 08-May-23 Revision8
Lecture 30 10-May-23 Revision