CS 135-Wed
CS 135-Wed
Algorithm Analysis and Design
Algorithm Analysis and Design
Embedded Files
Schedule : Wednesdays, 6pm to 9pm
Schedule : Wednesdays, 6pm to 9pm
Semester : 1st, AY 2020-2021
Semester : 1st, AY 2020-2021
Instructor : Henry N. Adorna
Instructor : Henry N. Adorna
email : <hnadorna@up.edu.ph>
email : <hnadorna@up.edu.ph>
Office : Rm 319
Office : Rm 319
3/F UPAE Centennial Hall
3/F UPAE Centennial Hall
The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct.
The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct.
Donald Knuth
Donald Knuth
This will be the official course website of CS 135-Wed, 6pm to 9pm Wednesdays class under Henry. This is a special course offered only for incoming graduate students needing this review of the introductory course for CS 210.
This will be the official course website of CS 135-Wed, 6pm to 9pm Wednesdays class under Henry. This is a special course offered only for incoming graduate students needing this review of the introductory course for CS 210.
This class will not meet physically but will be conducting classes remotely with occasional online meetings.
This class will not meet physically but will be conducting classes remotely with occasional online meetings.
Announcements for the class will be posted here, aside from emails that registered students will receive from the Instructor.
Announcements for the class will be posted here, aside from emails that registered students will receive from the Instructor.
Below will be the is the list of tentative topics to be covered for the class this unique semester of AY 2020-2021.
Below will be the is the list of tentative topics to be covered for the class this unique semester of AY 2020-2021.
Opposite the list of topics are provided with free online (videos) resources that hopes to guide the students in appreciating the course.
Opposite the list of topics are provided with free online (videos) resources that hopes to guide the students in appreciating the course.
Maligayang pagdating, Mabuhay!
Maligayang pagdating, Mabuhay!
Reminders
Reminders
a. You can discuss together to understand the problems in the problems sets and (also) to debate on possible ways to solve the problems, BUT each student must submit his own referenced suggested solutions.
a. You can discuss together to understand the problems in the problems sets and (also) to debate on possible ways to solve the problems, BUT each student must submit his own referenced suggested solutions.
c. You might want to look at the following online resource An Introduction to the Analysis of Algorithms and Algorithms by Robert Sedgewick et al.
c. You might want to look at the following online resource An Introduction to the Analysis of Algorithms and Algorithms by Robert Sedgewick et al.
d. You can please watch the following:
d. You can please watch the following:
Announcements
Announcements
Week 6 to 14
Week 6 to 14
Please read the following for the remaining topics for the semester:
Please read the following for the remaining topics for the semester:
Week 4 & 5
Week 4 & 5
a. Reading Summary for the half of the term were sent to the registered students.
a. Reading Summary for the half of the term were sent to the registered students.
c. There will be an online meeting on 28 October 2020, 11:30am to 1pm via Zoom. Invites are already sent to registered students.
c. There will be an online meeting on 28 October 2020, 11:30am to 1pm via Zoom. Invites are already sent to registered students.
d. You may be interested to read the following book (out-of-print) by Hopcroft and Ullmann, Foundation of Computer Science.
d. You may be interested to read the following book (out-of-print) by Hopcroft and Ullmann, Foundation of Computer Science.
e. The following readings/articles may help you appreciate computational complexity:
e. The following readings/articles may help you appreciate computational complexity:
oo0oo
oo0oo
Week 3
Week 3
- Readings for week3 were sent to registered students.
- Problem set 1b will be made available here within the week.
ooo0ooo
ooo0ooo
Week 2:
Week 2:
To help everyone to start doing some proof, you may consult the following:
To help everyone to start doing some proof, you may consult the following:
ooo0ooo
ooo0ooo
- Reading for Week have been sent to registered student this week via email by the instructor.
- Please inform the instructor if you're unable to receive them via email.
- Problem set 1a has been sent to all registered students. It is also available here.
- Please inform instructor if you're unable to receive one.
ooo0ooo
ooo0ooo
Week 1:
Week 1:
- Reading for Week have been sent to registered student this week via email by the instructor.
- Please inform the instructor if you're unable to receive them via email.
- First Online meeting (via zoom) will be on 18 September 2020; 12noon to 1:30pm.
- There after meeting will be as scheduled, Wednesdays 6pm to 9pm.
- Problem set 1a will be sent next week with the assigned readings for the week.
ooo0ooo
ooo0ooo
Week 0:
Week 0:
- This course, CS 135 is listed in UVLE. You must enroll to this course.
Students must activate their UVLe accounts; they need to log-in at UVLe using their DilNet accounts and (for first time users) must accept the UP Academic Use Policy after logging in.
Students must activate their UVLe accounts; they need to log-in at UVLe using their DilNet accounts and (for first time users) must accept the UP Academic Use Policy after logging in.
- You can now get the syllabus of the course here.
- Notes, problem sets and exercises for each topic will be posted weekly to this course webpage.
- You can also start watching relevant topics from The full playlist for Discrete Math I (Rosen, Discrete Mathematics and Its Applications, 7e)
- We will not have precise textbook for the course, but the following could the Main Course Reference(s) for this course:
- MIT 6.006 Introduction to Algorithms, Fall 2011 ; View the complete course: http://ocw.mit.edu/6-006F11 Instructor: Erik Demaine: Video Lectures are here!
- Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein , Introduction to Algorithms, 3ed; 2ed
Schedule of Activities
Schedule of Activities
Weeks
Weeks
week 0
week 0
Topics
Topics
Review of undergraduate Discrete Mathematics
Review of undergraduate Discrete Mathematics
Resources
Resources
The following are suggested video lectures available from YouTube:
Weeks
Weeks
week 1
week 1
Topics
Topics
Meet and Greet
Meet and Greet
Administrative for the course is here!
Administrative for the course is here!
Algorithmic Problems and
Algorithmic Problems and
Important problem types
Important problem types
Resources
Resources
The following are suggested video lectures available from YouTube:
What is an algorithm and why should you care? from Khan Academy
Algorithmic problem solving and interviews from Coursera
Weeks
Weeks
weeks 1 to 14
weeks 1 to 14
Topics
Topics
Main Course Topics
Main Course Topics
Resources
Resources
Main Course Reference(s)
MIT 6.006 Introduction to Algorithms, Fall 2011 ; View the complete course: http://ocw.mit.edu/6-006F11 Instructor: Erik Demaine: Video Lectures are here!
Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein , Introduction to Algorithms, 3ed; 2ed
The following are suggested video lectures available from YouTube:
Weeks
Weeks
weeks 2 to 5
weeks 2 to 5
Topics
Topics
Mathematical Foundation
Mathematical Foundation
- Methods of Proof
- Recurrence and Generating functions
- Computational Complexity: Upper and Lower Bound
- Complexity Classes
Resources
Resources
Notes on Mathematical Foundation
The following are suggested video lectures available from YouTube:
Weeks
Weeks
weeks 3 to 6
weeks 3 to 6
Topics
Topics
Mid-term Deliverables
Mid-term Deliverables
Resources
Resources
Problem sets 1a,1b,& 1c
Problem sets 1a,1b,& 1c
Weeks
Weeks
weeks 6 to 10
weeks 6 to 10
Topics
Topics
Analysis Techniques
Analysis Techniques
- Analysis by Counting
- Analysis of Recursive and Common Algorithm
- Analysis of Sorting and Order Statistics
- Analysis of Tree-based Algorithm
- Analysis of Graph Algorithm
Resources
Resources
Notes on Analysis techniques
The following are suggested video lectures available from YouTube:
7. Counting Sort, Radix Sort, Lower Bounds for Sorting from MIT OpenCourseWare
Weeks
Weeks
weeks 11 to 14
weeks 11 to 14
Topics
Topics
Analysis Design Techniques
Analysis Design Techniques
- Divide and Conquer
- Dynamic Programming
- Greedy Algorithm
- Backtracking
- Branch and Bound
Resources
Resources
Notes on Analysis Design Techniques
The following are suggested video lectures available from YouTube:
Weeks
Weeks
weeks 12 to 14
weeks 12 to 14
Topics
Topics
End-of-term Deliverables
End-of-term Deliverables
Resources
Resources
Problem sets 2a,2b, 2c & 2d
Problem sets 2a,2b, 2c & 2d
(online submission)
(online submission)
Interesting Resources
Interesting Resources
The following are suggested video lectures available from YouTube:
Donald Knuth: Algorithms, Complexity, and The Art of Computer Programming | Lex Fridman Podcast #62 by Lex Fridman
Algorithms for NP-Hard Problems (Section 19.3: Easy and Hard Problems) from Tim Roughgarden Lectures
NP-Complete Problems, lecture by Richard Karp form Computer History Museum
ALPHABETICAL LISTING OF A.M. TURING AWARD WINNERS: Juris Hartmanis
Algorithms by Robert Sedgewick and Kevin Wayne. video
Algorithms Course - Graph Theory Tutorial from a Google Engineer from freeCodeCamp.org
Introduction to Computational Complexity - A Tutorial on Algorithms and Complexity
Page updated
Report abuse