CS 240: Lecture 13 – Stacks and Queues Continued
Dear students: Today we continue our discussion of stacks and queues through some exercises. Postfix Evaluation Let’s see an example of an algorithm that uses a stack. Support you want to write code to evaluate an arbitrary arithmetic expression. Something of this form: $$7 + 5 \times 2 – 3$$ You might break the expression […]
CS 240: Lecture 12 – Stacks and Queues
Dear students: It’s time to introduce a new abstract data type: the queue. Like the stack, queue is only an interface. It can be implemented many different ways. In fact, Java doesn’t even have a Queue class. Today we’ll examine some of the possible implementations and look at some situations in which stacks and queues […]
CS 240: Lecture 11 – Linked List Lab
Dear students: Today we will devote our entire time together to a lab on linked lists. Follow these guidelines: You may work with one other person. If there’s an odd number of people, one group of three is permitted. Complete the lab using a single computer. Take turns at the keyboard. Talk to each other. […]
CS 240: Lecture 10 – Stack
Dear students: We’ve been talking about list as an abstract data type. We’ve also been talking about array lists and linked lists, which are two data structures that are commonly used to implement a list. Today we look at a new abstract data type: the stack. Stack A stack is an abstract data type representing […]
CS 240: Lecture 9 – Linked Lists
Dear students: We are in the middle of a discussion of linear structures and the complexities of their operations. We started with an array-based list, and now we move on to a linked list. Today we’ll examine how the two approaches to lists differ. Muddiest Points But first, I will address a sample of your […]
CS 240: Lecture 8 – Dynamic Arrays Lab
Dear students: Today we will devote our entire time together to a lab on dynamic arrays. Find the lab on the schedule on the main Canvas page. Follow these guidelines: You may work with one other person. If there’s an odd number of people, one group of three is permitted. Complete the lab using a […]
CS 240: Lecture 7 – Amortized Analyis of ArrayList
Dear students: Today we begin our application of complexity analysis to real live data structures that software developers use everyday. The first data structure to go under the microscope is the array-based list. Before that, though, we need to discuss one alternative view of the complexity classes. Limit Definitions Last week we looked at ways […]
CS 240: Lecture 6 – Analysis Lab Continued
Dear students: Today we will continue analysing algorithms in the lab exercises we started on Friday. TODO Read 7.01-7.03 in OpenDSA. Read Amortized Analysis Explained. Keep working on PA1. Run into issues now, while there’s time to address them. See you next time. Sincerely,
CS 240: Lecture 5 – Analysis Lab
Dear students: Today we will practice measuring or analysing algorithms in lab exercises. But first we need to muddy the waters just a bit more. What is cost function of this algorithm? public static boolean contains(int target, int[] numbers) { for (int number : numbers) { if (number == target) { return true; } } […]
CS 240: Lecture 4 – Asymptotic Complexity
Dear students: If I asked you how fast you can run, you probably wouldn’t give me a number. Rather, you’d ask me how far. To get a complete picture of your speed, I might ask how fast you run a mile, a 5K, a 10K, and a marathon. Similarly, when I ask an algorithm how […]