Author

Martine

Browsing

VERY IMPORTANT: ALL students SHOULD HAVE THEIR TEXTBOOKS BY DAY 1 of classes!!!

Course Description: The purpose of this course is to present the student with the mathematical techniques used for analyzing the time and space performance of computer algorithms.  The focus will be on the practical application of these techniques to designing efficient algorithms.  The following topics will be covered: asymptotic notation, recurrences, lower bounds for worst case and average case, dynamic programming, searching algorithms, sorting algorithms, graph algorithms, and if time allows, parallel algorithms, string matching algorithms.

Textbooks:

It is very important that ALL students have their books from Day 1.

  • “Introduction to Algorithms”, by Cormen, Leiserson, Rivest, and Stein, Third Edition, McGraw Hill
  • “Algorithms in a nutshell”, by Heineman, Police, and Selkow, by O’Reilly, 2008.

Exams: There will be two examinations, some written assignments, homework assignments, quizzes (announced and unannounced — but roughly one quiz every week), two projects, and a presentation.  On of the projects will involve testing an existing library for performance purposes. The other project will involve programming some algorithms and carrying out an analysis on their performance.  For the presentation, students will present an algorithm research paper from a journal or conference, preferably recent.

Grades:
Test 1                                         20%
Test 2                                         20%
Presentation                               8%
Quizzes                                     15%
Homework assignments         10%
Projects                                       22%
Class participation                      5%

SUMMARY OF IMPORTANT DATES:

ANNOUNCEMENTS:

  • Week 14:
    • Monday November, 21st: Project #2 Presentation by the team working on Convex Hulls
  • Week 12:
    • Short quiz on Monday and review for the exam
    • Long quiz on Wednesday
  • Week 11:
    • Group quiz on Monday!
    • Grades for project 1 are ready: please stop by my office if you want to know your grade.
    • The second extra credit assignment is now available on this page.
    • Wednesday: office hours are exceptionally changed! they will be from 10:30 to 11:45 instead of the usual time.
  • Week 10:
    • Quiz on Monday!
  • Week 9:
    • Quiz on Monday!
  • Week 8:
    • Quiz on Monday! and Quiz on Wednesday!
  • Week 7:
    • Quiz on Monday! (on Chapter 4) and on Wednesday!
    • Project #2: make plans to meet with me asap as a group of all the people who picked the same project topic area! Check: http://meetwith.me/mceberio to suggest meeting times (suggest 3 meeting times of half an hour each so that I can pick)
  • Week 6:
    • The first exam is scheduled on Wednesday September, 28th.
  • Week 5:
    • Quiz on Monday!
  • Week 4:
    • Quiz on Monday!
    • Remember that you have to send me your projects’ preferences!!!
    • Project topics (for project 2) have been assigned: check your mailboxes!
  • Week 3: No class on Monday: Labor Day. As a result, the office hours of Monday are moved to Tuesday from 1:30pm to 2:30pm / Quiz on Wednesday!

WHAT TO EXPECT — some of this semester’s milestones:

  • An article to summarize: Due by November 4!
    • See the guidelines for this assignment
    • Make sure that you joined the shared folder to have access to the articles for your assignment
    • In case you forgot, you can review your individual article assignment here
  • Semester-long projects: Due by the end of week 14!
    • A list of projects (for projects #2) will be proposed during week 3
    • Students need to have chosen a project (#2) by the end of the last course of Week 4
    • Assignment #1 (group assignment): write a tutorial. Due by Friday October, 28
  • Short projects: Due on October 21, 2011!!!
  • First midterm exam on September 28th (week 6), topics covered in the exam
  • Final exam on Monday November, 16th (week 13)

MATERIAL:

ASSIGNMENTS:

  • Note: unless otherwise specified, homework will be due via email on Wednesdays at 5pm (from the students whose names are called in class).
  • Week 12: (Nov. 7 to Nov. 11)
  • Week 11: (Oct. 31 to Nov. 4)
    • Article summary assignment — Due by Friday November, 4
    • Reading assignment: same as week 10.
    • Homework assignment:
      • Turn in either of the following proofs: proof that the Huffman’s code algorithm has the greedy choice property; or proof that the greedy approach to the fractional knapsack problem (as discussed in class) has the greedy choice property.
      • Turn in a proof that the 0-1 knapsack problem does not have the greedy choice property.
  • Week 10: (Oct. 24 to 28)
    • Extra-credit assignment: Proof of the master theorem in your own words (more details to come soon) — Due by Friday October, 28
    • Project #2: Tutorial due Friday October, 28
    • Reading assignment:
      • Chapters 15 and 16 from the Cormen textbook
      • Chapter 26 of the Cormen textbook and Chapter 8 of Algos. in a Nutshell
    • Homework assignment:
      • (not to be turned in… yet 🙂 ): Exercises 16.1.* from the Cormen textbook
  • Week 9: (Oct. 17 to 21)
    • Project #1: Final deadline on Friday October, 21 at 11:59pm (see the project guidelines)
    • Homework assignment: Deadline extended to Monday October, 24th
      • Problem 15.3 from Cormen textbook
    • Reading assignment:
      • Chapters 15 and 16 from Cormen texbook
      • pp. 165-171 of Algorithms in a Nutshell
  • Week 8: (Oct. 10 to 14)

    • Homework assignment:
      • Exercises 15.1.5 (p. 370 of Cormen textbook), 15.2.1 and 15.2.3 (p. 378) are to be turned in; hints of solutions now available.
      • Reminder: besides the exercises to be turned in, you have to practice on as many exercises as possible
    • Reading assignment:
      • Chapters 15 and 16 from Cormen texbook
      • pp. 165-171 of Algorithms in a Nutshell
  • Week 7: (Oct. 3 to 7)
    • Homework assignment:
      • Problem 4.6 of Introduction to Algorithms; solution hints now available
    • Reading assignment:
      • Chapter 4 of Introduction to Algorithms
      • Part II (Chapters 6,7,8) and III (Chapters 10, 11, 12) of Introduction to Algorithms: the purpose of this reading assignment is to refresh  everybody’s mind about the material of the course that is a pre- requisite to CS5350.
  • Week 6: Week of Exam 1!!!
    • Homework assignment: no homework to turn in. However, students are encouraged to practice on the exercises from the book.
    • Reading assignment: review of all chapters that were assigned previously
    • Project #1 (reminder): intermediate deadline coming up this Friday! (see the project guidelines if you don’t remember what you have to do)
  • Week 5:
    • Homework assignment: Solution hints
      • To be turned in: Problems 2.1, 3.6
      • Not to be turned in but likely to appear on a quiz or test: all exercises 3.1.*; Problem 3.4
    • Reading assignment: Chapters 3 and 4 of Introduction to Algorithms
  • Week 4:
    • Homework assignment: 2.2.1, 2.2.2, Problem 2.3 (due Wednesday of Week 4 by 5pm / via email); Solution Hints
    • Reading assignment: Chapter 2 Section 2 of Introduction to Algorithms, Chapters 2 and 4 of Algorithms in a Nutshell
  • Week 3:
    • Homework assignment: 2.1.3 and 2.1.4, from Introduction to Algorithms
    • Reading assignment: Introduction to Algorithms, Chapter 2, Sections 2.1 and 2.2.
  • Week 2:
    • Same reading assignments as for Week 1
    • Homework assignment: TBA (due Wednesday September, 5th)
  • Week 1:
    • Read Chapters 1 and 2 of both textbooks
    • For those of you who did not attend Monday’s session:
      • Read, print, sign, and turn in the course syllabus
      • Check your email: I sent you documents for you to work on on Wednesday, in groups

Additional material:

Note: More information (such as assignments, reminders for due dates, quizzes, exams) will be posted on this page as the semester goes.

VERY IMPORTANT: ALL students SHOULD HAVE THEIR TEXTBOOKS BY DAY 1 of classes!!!

Course Description: The purpose of this course is to present the student with the mathematical techniques used for analyzing the time and space performance of computer algorithms.  The focus will be on the practical application of these techniques to designing efficient algorithms.  The following topics will be covered: asymptotic notation, recurrences, lower bounds for worst case and average case, dynamic programming, searching algorithms, sorting algorithms, graph algorithms, and if time allows, parallel algorithms, string matching algorithms.

Textbooks:

It is very important that ALL students have their books from Day 1.

  • “Mathematical Logic for Computer Science”, by Lu Zhongwan, Second Edition, World Scientific Publishing.
  • “Logic in Computer Science: Modeling and Reasoning about Systems”, by Michael Huth, Cambridge University Press.

Additional recommended reading:

  • Introduction to Mathematical Logic, by Elliott Mendelson, Fifth Edition, CRC Press.
  • Sets, Logic and Maths for Computing (Undergraduate Topics in Computer Science), by David Makinson
  • The Nuts and Bolts of Proofs, Third Edition: An Introduction to Mathematical Proofs, by Antonella Cupillari
  • How to prove it: a structured approach, by Daniel Velleman

Exams: There will be two tests, some written assignments, quizzes (announced and unannounced), a project and a presentation.  For the presentation, students will individually present an algorithm research paper from a journal or conference, preferably recent.

Grades:
Test 1                                         20%
Test 2                                         25%
Presentation                              10%
Quizzes and Assignments          15%
Project                                       25%
Class participation                      5%

Announcements:

  • Week 5: the office hours of Tuesday will be moved to Tuesday morning: 10am to 11:30am and Wednesday morning from 11am to noon.
  • No class on February 1st: an assignment will be given in replacement of the class / to be posted later
  • Midterm exam on March 8th! topics are everything we have covered since the start of the semester. The exam will be an hour and 20 minutes long. If you cannot make it, you should let me know BEFORE March 8th and reschedule the exam by March 15th at the latest.
  • No class on March 22nd: an assignment will be given in replacement of the class / to be posted later
  • No class on Cesar Chavez day (March 31)
  • Don’t forget that April 25 is the deadline for you to pick your project option (presentation or deliverables only)
  • Final examination on April 28!!! topics to be covered are everything we covered since the start of the semester. If you cannot make it, you should let me know BEFORE April 28th and reschedule the exam by May 5th at the latest.

What to expect — some of this semester’s milestones:

  • Semester-long projects:
    • List of projects
    • Projects will be proposed during week 3: see below for the list of projects / also sent as email to all students enrolled in the class
    • Students need to have chosen a project by the end of the last course of Week 5 (i.e., February, 17 at 3pm) Week 6 (i.e., February, 24 at 7pm): extension due to severe weather early February
    • Week 15 and week of the finals: project presentations
  • First midterm exam during week 8, on Tuesday March 8st.
  • Article presentations: week 12.
  • Final exam on Thursday April, 28th

Material:

Assignments:

  • Week 11:
    • Reading assignment: Chapter 3, Sections 4, 5, and 6, as well as Chapter 5 from Mathematical Logic for Computer Science
    • Homework assignment, due April 14:
      • exercises 3.4.2 [3,4], 3.4.3 [1,2,5,6], and 3.6.1, from Mathematical Logic for Computer Science
    • Project assignment #2, due April 18: write a tutorial-type document about the topic of your project; to be done in team; here are detailed guidelines for assignment #2
  • Week 10:
  • Week 9:
    • Reading assignment: predicate logic, chapter 3 of Mathematical Logic for CS and  chapter 2 (2.1 and 2.2) of Logic in Computer Science
    • Homework assignment:
      • exercise 2.1 [1,2,3] p. 157 of Logic in Computer Science
      • exercises 2.6.3 [1,4] and 2.6.5 [3], p. 57, from Mathematical Logic for CS
  • Week 8:
    • Reading assignment: predicate logic, chapter 3 of Mathematical Logic for CS and  chapter 2 (2.1 and 2.2) of Logic in Computer Science
    • No homework assignment: week of midterm exam
    • Project: description (both individual description and group questions) are due on March 11th at 7pm
  • Week 7:
    • Reading assignment: pages 42 to 65 of Mathematical Logic for CS
    • Homework: exercises 2.5.3 [3,4] and 2.5.2 [2,6] of Mathematical Logic for CS
  • Week 6:
    • Reading assignment: same as for week 5, more specifically pages 42 to 65 of Mathematical Logic for CS
    • Homework:
      • Exercises 2.3.1, 2.4.1, 2.4.4, 2.4.5, from Mathematical Logic for Computer Science
  • Week 5:
    • Reading assignment:
      • Chapter 2 of Mathematical Logic for CS
      • Chapter 1, sections 1.1, 1.3, 1.4, 1.5 of Logic in CS
    • Homework will be given in class: due Feb. 22
    • Quiz on Thursday!
  • Week 4:
    • Reading assignment: propositional logic (introduction, description, use)
    • Projects: brainstorm about a CS project that involves logic; write a paragraph describing it, due on Feb. 15 (Tuesday of week 5)
    • Quiz on Thursday!
  • Week 3:
    • Reading assignments: sets and functions (Chapter 1 of the first textbook, or notes posted on this website)
    • Homework due on Thursday February, 3:
      • exercises 8 and 11 of the list of exercises titled “Exercises on Induction”
      • exercise 2 of the list of exercises titled “Induction”
      • exercises 3 and 4 of the list of exercises titled “Exercises on Sets and Functions
    • Assignment for February, 1: a prolog assignment due on February, 8 !!! Now due on Feb. 15 !!!.
  • Week 2:
    • Homework due on Thursday January, 27:
  • Week 1: due on Thursday January, 20
    • Review sets and functions
    • Homework [DUE and randomly checked]: List several (at least 3) applications of these in computer science: detail and justify each item of your list.

Note: More information (such as assignments, reminders for due dates, quizzes, exams) will be posted on this page as the semester goes.

VERY IMPORTANT: ALL students SHOULD HAVE THEIR TEXTBOOKS BY DAY 1 of classes!!!

Course Description: The purpose of this course is to present the student with the mathematical techniques used for analyzing the time and space performance of computer algorithms.  The focus will be on the practical application of these techniques to designing efficient algorithms.  The following topics will be covered: asymptotic notation, recurrences, lower bounds for worst case and average case, dynamic programming, searching algorithms, sorting algorithms, graph algorithms, and if time allows, parallel algorithms, string matching algorithms.

Textbooks:

It is very important that ALL students have their books from Day 1.

  • “Introduction to Algorithms”, by Cormen, Leiserson, Rivest, and Stein, Third Edition, McGraw Hill
  • “Algorithms in a nutshell”, by Heineman, Police, and Selkow, by O’Reilly, 2008.

Exams: There will be two tests, some written assignments, quizzes (announced and unannounced), a project and a presentation.  The project will involve programming some algorithms and carrying out an analysis on their performance.  For the presentation, students will individually present an algorithm research paper from a journal or conference, preferably recent.

Grades:
Test 1                                         20%
Test 2                                         20%
Presentation                              15%
Quizzes and Assignments          15%
Project                                       20%
Class participation                      5%

Announcements:

  • Weeks 15 and 16 (finals’ week):
    • Projects presentations
  • Week 14:
    • More work on projects, no class
    • Projects reports due by Sunday November, 28th at 7pm via email to your instructor
  • Week 13:
    • Final exam on Monday November 15th
    • Work on projects on Wednesday: no class / instructor available for questions
  • Week 12:
    • Presentations of articles in class: 5- to 7-minute presentations
  • Week 11:
    • Long quiz on Monday November, 1 at 1:30 until 2:50pm: objective = to get ready for the exam scheduled on Monday November, 15.
  • Week 6:
    • First exam on Monday September, 27 at 1:30pm until 2:50pm.
    • There will be no office hours since Dr. Ceberio will be out of town attending a conference.
  • Week 5: The Monday office hours will exceptionally be moved to Tuesday from 10am to noon.
  • Week 3: Since Monday is a day off, office hours from Monday will be moved to Tuesday from 10am to noon.

What to expect — some of this semester’s milestones:

  • Semester-long projects:
    • Projects will be proposed during week 3: see below for the list of projects / also sent as email to all students enrolled in the class
    • Students need to have chosen a project by the end of the last course of Week 4 (i.e., September, 15 at 3pm):
    • IMPORTANT! Project assignments were sent out to all students on Wednesday September, 15. You should all be now working on them as all projects require your full attention until the end of week 14.
    • Project meetings with instructor: Week 9-10 / week 11-12 / week 14
    • The second half of week 13 will be dedicated to working on your projects
    • Week 14: no class but you will have to meet with me to report on your project’s progress
    • Week 15 and week of the finals: project presentations
  • First midterm exam on September 27th
  • Article presentations: week 12 (Nov. 8 and 10); articles will be given to students on October 27th.
  • Final exam the Monday November, 15th

Material:

Assignments:

  • Week 10:
    • Reading assignment: Chapter 8 of Algorithms in a Nutshell and Chapter 26 of Introduction to Algorithms
    • Homework:
      • Prepare a presentation of the Ford-Fulkerson method. Show how it can be implemented different ways with different performances.
      • Prepare a presentation of the example of the FF method as shown on your book, p. 726.
  • Week 9:
    • Reading assignment: Chapters 16 and 17 of Introduction to Algorithms.
    • Extra-credit due by November 3rd on paper
    • Homework due by October 27 at the start of the class (randomly picked) + some exercises given in class on showing the greedy choice property
  • Week 8:
    • Reading assignment: Chapters 15 and 16 of Introduction to Algorithms, Chapter 6 of Algorithms in a Nutshell
    • Homework assignment:
      • Work on the matrix chain multiplication problem, as described in class, for Wednesday October, 13
      • More homework to be randomly picked-up next Monday (October 18): description of exercises
  • Week 7:
    • Reading assignment: Chapters 15 and 16 of Introduction to Algorithms, Chapter 6 of Algorithms in a Nutshell
  • Week 5:
    • Reading assignment: Chapters 4 and 5 of Introduction to Algorithms
    • Homework assignments:
      • Exercises 4.1.1, 4.1.2, 4.1.3, 4.1.5
      • Problems 3.1 and 3.4
    • Extra-exercises to work on:
      • 4.3.1, 4.3.2, 4.3.3, 4.3.6, 4.3.9
      • 4.4.2, 4.4.4, 4.4.5, 4.4.6, 4.4.7, 4.4.8
    • Extra credit: Due via email by Friday Sept. 24 at 7pm: Write an explanation of the proof of the master theorem in your own words (potential for extra points: 10 points towards the sum of the exams’ grades)
  • Week 4:
    • Reading assignment: Chapter 4 of Introduction to Algorithms, revision of Chapters 1 and 2 + Chapters 3 and 4 of Algorithms in a Nutshell
    • Homework assignments:
      • Prove all properties of transitivity, reflexivity, etc. from your textbook Introduction to Algorithms that we did not do together in class
      • Exercises 3.1.2, 3.1.4, 3.1.5, 3.1.7, 3.1.8
  • Week 3: Read Chapter 3 of Introduction to Algorithms and Chapter 2 of Algorithms in a Nutshell. There will be a quiz on Wednesday September, 8th on the whole 3.2 section.
    • Homework: Exercises given in class and exercises 3.2.1 and 3.2.2 from Introduction to Algorithms
    • Exercises given in class were:
      • To show how the recursive Fibonacci number computation is an example of Divide and Conquer algorithm
      • To present one algorithm (different from what we saw in class) that is a Divide and Conquer algorithm, and show that it is actually one
      • To do the problem on Horner’s rule from the Introduction to Algorithms textbook
      • To do the problem on Insertion and Merge sort from the Introduction to Algorithms textbook
  • Week 2: Read Chapters 2 and 3 of Introduction to Algorithms
  • Week 1: Read Chapters 1 and 2 of both textbooks

Some material:

Note: More information (such as assignments, reminders for due dates, quizzes, exams) will be posted on this page as the semester goes.

Syllabus available here

Important information is also available about: how and when to contact your instructor, labs, etc.

This course is a survey of classic algorithms and data structures, useful for sorting, manipulating graphs, storing data collections and mappings. Students will acquire an understanding of generalization techniques for evaluating the complexity of these algorithms, and they will be able to apply these algorithms to a wide range of computer science problems. Introductory techniques for determining correctness and evaluating complexity will be presented. Students are expected to master basic skills and to develop an intuitive understanding of how the surveyed analysis techniques are commonly used. The main objective is that students develop their critical thinking skills and become able to make an appropriate choice of data structures given any problem, and to justify their choice in an articulate explanation.

As far as assignments and exams , there will be:

  • reading assignments, and homework assignments (randomly checked);
  • (announced AND un-announced) quizzes throughout the semester;
  • programming assignments: 4 or 5 of them (most probably 5) — turning all of them and making at least a C at each of them are required to pass the class;
  • 3 mid-terms;
  • 1 final exam.

Teaching Assistant
The labs will be held by a teaching assistant. Name and e-mail address of your TA: Jaime Nava, jenava@miners.utep.edu

Peer Leading Sessions
Peer Leading sessions will be held each week during half of the lab times. Two peer-leaders are in charge of those sessions: Cesar Chacon, crchacon@miners.utep.edu, and ??, ??@utep.edu. For more information about peer-leaders and peer-led team learning, go to this website.

Textbook: Data Structures outside in, with Java, by Sesh Venugopal, Eds. Pearson Prentice Hall.

This class will meet every Tuesday and Thursday, from noon to 1:20pm in room 308.

The content of classes is (tentatively) expected to be as follows:

  • week #1: Presentation of syllabus. Introduction to algorithm analysis.
  • week #2: Algorithm analysis
  • week #3: Algorithm analysis
  • week #4: Stacks
  • week #5: Queues / Discrete Event Simulation / MT1
  • week #6: Discrete Event Simulation / Hash tables
  • week #7: Hash tables / Trees: general trees, traversals / Binary trees
  • week #8: Trees: binary trees, binary search trees, algorithms, classical problems and algorithms
  • week #9: Balanced trees: AVL, heaps
  • week #10: Trees: cont’d / MT2
  • week #11: Review of sorting algorithms: analysis, purpose, problems -> mostly about heap sort
  • week #12: Graphs: definition, use
  • week #13: Graphs: classical problems and algorithms / MT3
  • week #14: Advanced topics
  • week #15: General reviews
  • week #16: week of the final exam