Textbook / Software

• Shaffer, Data Structures and Algorithm Analysis (2013)
• OpenDSA CS3
• Recommended, not required: Weiss, Data Structures and Algorithm Analysis in Java (on reserve at library)
• Install Java: Oracle JDK
• VSCode
• Install IntelliJ: IntelliJ IDEA Ultimate Edition
  • Apply for a free license using your purchase.edu email
• GitHub classroom (instructions on BrightSpace)

Course Expectations

• Combination of lectures and asynchronous notes / videos
• Small group meetings from time to time to catch up
• Grading scheme on next slide.
• I include real “technical interview” questions as much as I can.

Grading

• 30% Programming Projects (3 x 10%)
• 20% Homework assignments (4-5)
• 10% Quizzes, class exercises, class participation
• 20% Presentations (4-5 throughout the semester)
• 20% Final Project (likely in groups or pairs)

Some Big Oh Relationships

• \(n = O(n^2)\)
• \(n^2 = O(n^3)\)
• \(\log_2(n) = O(\log_3(n)) = O(\ln(n))\): “logarithmic time”
• \(n^k = O(2^n)\) for any constant \(k\)
• Algorithms that run in \(O(n)\) steps: “linear time”
• \(O(n^2)\): “quadratic”
• \(O(n^k)\): “polynomial”
• \(O(2^n)\): “exponential”
• \(O(1)\): “constant”

Big Oh Cheat Sheet

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    // O(1) stuff happening here
    ...
  }
}

• The above snippet runs in \(O(n^2)\) time.
• What would something that runs in \(O(n)\) look like?
• \(O(\log(n))\)?

Data Structures

• A data structure is a way of organizing data in memory.
• Often: problems can be simplified by using the right data structure.

Example

• arrays. Built in to the Java language.
• ArrayList. Defined in the standard library.

int[] arrayofInts = new int[10];
ArrayList<Integer> list = new ArrayList<>();

• Both: random-access list of data (in this case, integers).
• What is different about these two data structures?

Part 1

First, just figure out: given \(n\), how to output the \(n\)-th row of that pattern:

1, 2, ..., n

Running time?

Part 2

Now use your method in part 1 to output \(n\) rows so that, for each \(i\) from \(1\) to \(n\), you output the row \(1, 2, \ldots, i\).

Running time?

Exercise

Work on these with a partner or in small groups.

1. Start with part 1.
2. First describe the algorithm to each other. Do this on paper, using pseudocode, but hopefully it should be easy enough to translate to Java.
3. Next, analzye the running time of your algorithm.
4. If you have time, you can implement it on VSCode or IntelliJ to test it out.
5. Then go back to part 2 and do the same thing. Describe the algorithm to each other, and then analyze the algorithm.

GitHub Classroom

Link to assignment

• Read through it for homework: lots of info about git/GitHub
• For now: put in your code in Triangle.java
• Answer the question about running time in the README.md file (toward the bottom)