CS计算机代考程序代写 data structure algorithm Hive Lecture 3 – Linked Lists

Lecture 3 – Linked Lists

Lecture 14

Midterm Exam Review

EECS 281: Data Structures & Algorithms

Good News!

http://phdcomics.com/comics/archive.php?comicid=2022

2

http://phdcomics.com/comics/archive.php?comicid=2022

Times

• When: Thursday October 21

– 7:00pm – 9:20pm (Ann Arbor time, 140m)

• Two hours + 20 minutes for down/uploads

• Extended times start at the same time

– Ends 1 hour later for 1.5x time, 2 hours for 2x

3

Locations

• Online, via Canvas and Gradescope

• All questions are shown in your Canvas

“Quiz”

– Submit the multiple choice answers inside

that Canvas Quiz

– Submit written problems on Gradescope

• DO NOT submit until done with both parts

– Honor pledge on a separate Canvas Quiz, fill

out the next day
5

Downloading Starter Files

• In the past we had a link within the exam

to the starter files, but some students

couldn’t open the links

• The starter files are on the autograder

under the Exams tab

• DO NOT DOWNLOAD EARLIER THAN

YOU TAKE THE EXAM

• Don’t rush to download, read question first

6

During the Exam

• We will set Piazza to private posts by

default

• If you have a question, post on Piazza

privately (do not followup a public post!)

• Move on to another question and check

back for an answer in a few minutes

• Set your browser to fill the screen,

standard zoom factor (otherwise some

pictures disappear)
7

Policies

• Use anything that WE have given you

– Lecture PDFs, labs, etc.

• During a “normal” semester we allow a

cheat sheet

• Still a good idea to make one

– Important information all in one place

– Writing by hand improves long-term memory

• Engineering Honor Code applies

8

Multiple Choice Portion

• 24 questions, 2.5 points each (60 points)

• 4-5 possible answers per question

• No deduction for being wrong

– Make sure to answer all 24 questions

– ONE answer per question

10

Exam Itself

• All questions are in the Canvas “quiz”

– Multiple choice will be answered in the “quiz”,

as you do for Labs

– Written questions will be answered on

Gradescope, as you do for lab written

problems

• DO NOT SUBMIT THE QUIZ UNTIL YOU

ARE DONE WITH BOTH PARTS

– Once you submit, you cannot see the written

questions
11

Display Issue

• The exam will be have a “time limit” of the

longest allowed time (usually 2x or 260

minutes)

– Canvas only allows one setting for this

• Each student will have a time limit (140

minutes for most, more for SSD students)

• It may tell you that you “started late”

because you’re not getting 4+ hours

– This is a display issue only; non-SSD

students have 140 minutes start – end
12

Check Remaining Time

• If you have an SSD accommodation for

extended time, check it when you start

• If it’s wrong, post on Piazza, and we can

fix it during the exam, adding the time

you’re allowed, and Canvas will adjust

your remaining time

• Once you submit the quiz, we can’t add

time

13

Study Materials

• Practice exam posted on Canvas

– Answers auto-reveal after last lecture

• Lecture slides and recordings

• In-class exercises

• Lab materials

• Projects

• Study group

16

Topics

• Everything we have covered so far,

especially:

• Complexity analysis, including recurrences

• Contiguous (array) versus linked

containers

• Stacks, queues and priority queues

• Binary heap (not pairing) and Heap Sort

• Elementary, Quick and Merge sorts

• Strings and sequences 17

Answering Coding Questions

• If you decide you want a helper function,

write it above the given function

• If you need a structure, write that inside

the given function, or above it

– Some coding problems given in some

semesters can ONLY be solved if you create

a struct (or use a pair<>)

18

Coding Questions – Lines

• How many lines of code is this?

if (x > 0) result = 0;

• 2 lines of code, same as this:

if (x > 0)

result = 0;

20

Coding Questions – Lines

• How many lines of code is this?

if (x > 0) {

result = 0;

return result;

} // if

• 3 lines of code: the closing curly brace
never counts as a “line of code”

21

Coding Questions – Lines

• How many lines of code is this?
if (x > 0)

result = 0;

else

result = x;

• 4 lines of code, the else statement counts
as a line

• One line with ternary operator:
result = (x > 0) ? 0 : x;

22

Coding – Container of struct

• Once you create a structure, how can you

easily add a member of that structure to a

container? (OBTW: line count = 5)
struct WordCount {

string word;

int count;

};

vector vwc;

vwc.push_back({ “abc”, 1});
23

Coding Questions – Libraries

• Each coding question will tell you what you

can or cannot use from the C and STL

libraries

• The function header that we give you will

not be part of the line limit

– If you add a struct or helper function, those

lines will count

– If this is a reasonable way to solve the

question, it is already factored in the line limit

24

Coding Questions – Integers

• For loop variables, use whatever type

makes sense (size_t, int, etc.)

– You don’t have to worry about implicit

conversions on loop variables

• If we pass a vector to your function
and you need to keep a copy of one or

more of those values, use an int variable,
or a container of int

– Stay consistent with data

25

Complexity Analysis

0

5

10

15

20

25

0 1 2 3 4 5 6 7 8 9 10

1

log n

n

n log n

n2

2n

26

What is the complexity? Θ(…)
1 int* bsearch (int* lo, int* hi, int val) {
2 while (hi >= lo) {
3 int* mid = lo + (hi – lo) / 2;
4 if (*mid < val) lo = mid + 1; 5 else if (*mid > val) hi = mid – 1;
6 else return mid;
7 } // while
8 return nullptr;
9 } // bsearch()

10 void f(int *out, const int *in, int size) {

11 for (int i = 0; i < size; ++i) { 12 out[i] = 1; 13 for (int j = 0; j < size; ++j) { 14 if (i == j) 15 continue; 16 out[i] *= in[j]; 17 } // for 18 } // for 19 } // f() 27 What is the complexity? Θ(...) • Write the recurrence relation • Solve 1 void merge_sort(Item a[], int left, int right) { 2 if (right <= left) 3 return; 4 int mid = left + (left - right) / 2; 5 merge_sort(a, left, mid); 6 merge_sort(a, mid, right); 7 merge(a, left, mid, right); 8 } // merge_sort() 29 Containers • What is the best container if it will be used primarily to locate objects within it using binary search? • What is the best container if new objects will often be added immediately before specific existing objects? • What is the best container if you must store a small number of very large objects. Memory is scarce and the most important consideration is to store as many of these objects as possible in the available space? • Options: singly-linked list, doubly-linked list, vector • Also: WHY? 32 Containers • What is the worst container if you must store a large number of one byte items and memory is the scarcest resource? • What is the worst container if you will frequently insert new items anywhere within the structure? • What is the worst container if you will frequently insert new items at the beginning of the structure? • Options: singly-linked list, doubly-linked list, vector • Also: WHY? 34 Stacks and queues • Implement a queue using two stacks. Given the class below, write the pop() function. 1 class MyQueue { 2 stack s1, s2;

3 public:

4 void push(int num) {

5 s1.push(num);

6 } // push()

7 void pop();

8 int front();

9 }; // MyQueue

36

Sorting

Unless stated otherwise, use the best (most adaptive)

version of a sort that we’ve developed. Which sort is best

in these circumstances?

• Array that is “almost” already sorted

• Very small array

• Medium size array

• Large array (about as big as main memory)

• Very large tape drive

You’re using a quicksort on a very large input, and it’s

taking longer than normal. What happened?
38

Binary Heaps

• Draw the underlying

array for this heap

• Push the value 47

– Use fixUp()

• Draw the resulting

tree and array

81

18 14

4

1 59 7

2

41

Priority Queues

• What is the complexity?

Unordered

Array

Ordered

(Sorted) Array

Binary Heap

create(range)

push()

top()

pop()

43