DOC PREVIEW
CMU CS 15122 - Lecture Notes on Lists and Queues

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Lecture Notes onLists and Queues15-122: Principles of Imperative ComputationFrank PfenningLecture 7September 14, 20101 IntroductionIn this lecture we first review amortized analysis with another example, thistime studying binary counters. Then we will introduce queues as a datastructure and linked lists that underly their implementation. In order toimplement them we need recursive types, which are quite common in theimplementation of data structures.2 Amortized Analysis of Binary CountersA binary counter is a sequence of bits, representing a number in binaryform, that can be incremented. We do not presume a fixed precision, butallow the counter to be extended in case it overflows. To simplify the anal-ysis we assume we start at 0 and count upwards.We are interested in measuring the cost of incrementing the counter interms of the number of bits we have to flip. For example, incrementing 0[2]to 1[2]requires 1 bit flip, incrementing 1[2]to 10[2]requires 2: we comple-ment the lowest bit, and then we add another digit on the left, which weconsider the same as flipping a (hypothetical) 0 to 1.What is the cost of a single increment? It looks mostly like constanttime, but not quite. For example, when the number is 11111111[2]then theincrement will take 9 bit flips, which is equal to the number of bits we have(8), plus 1. In general, after we incremented n = 2ktimes, we will havek + 1 bits in our representation. So the maximal number of bit flips duringa single increment is O(k) = O(log(n)).LECTURE NOTES SEPTEMBER 14, 2010Lists and Queues L7.2But what is the cost of incrementing a counter n times? Naively mul-tiplying we might think the cost is O(n ∗ log (n)), but we might suspect itcould be less, like O(n), if we analyze the situation more carefully. A perfectexample where we can try an amortized analysis!Let’s do some counting of bit flips, starting at 0, to see if we can forma conjecture. Since we are working with binary numbers throughout weomit the base[2].number op flips0 inc 11 inc 210 inc 111 inc 3100 inc 1101 inc 2110 inc 1111 inc 41000 inc 11001Looking at the structure we see at on each increment, there is exactly oneflip from 0 to 1, and some variable number of flips from 1 to 0. Let’s sepa-rate these out.number op 0 → 1 1 → 00 inc 1 01 inc 1 110 inc 1 011 inc 1 2100 inc 1 0101 inc 1 1110 inc 1 0111 inc 1 31000 inc 1 01001The question is how to account for the 1 → 0 flips. The idea behindamortized analysis here is to set aside a constant number of tokens oneach increment, so that we have enough saved up to perform the 1 → 0flips. Recall that each token represents an operation we could have per-formed and stayed within constant time for each of the n increments, butdid not. Therefore, we can perform these operations later without violatingthe O(n) bound for the total number of n increments.LECTURE NOTES SEPTEMBER 14, 2010Lists and Queues L7.3The crucial insight here is that on each increment we create exactly onenew 1 that was not in the previous number, namely the 0 → 1 flip. So,if we put aside one token for every increment, we should have one tokenfor every digit 1 in the number. That’s enough to pay for the flips 1 → 0,because the number of these flips on each increment is bounded by thenumber of 1’s.Let’s run through this again and count the number of tokens we wehave. We save one on each operationtokensbefore inc number op 0 → 1 1 → 0tokenssavedtokensspent0 0 inc 1 0 +1 01 1 inc 1 1 +1 −11 10 inc 1 0 +1 02 11 inc 1 2 +1 −21 100 inc 1 0 +1 02 101 inc 1 1 +1 −12 110 inc 1 0 +1 03 111 inc 1 3 +1 −31 1000 inc 1 0 +1 02 1001From this table we form the conjecture that if we save a token on everyincrement, and we spend a token for every 1 → 0 flip during an increment,then we always have exactly as many tokens as 1’s. Since number of 1’s cannever become negative, the number of tokens never becomes negative.To prove this, we note two things. First, when we start we have notokens saved and also no 1’s in the number, so the invariant holds.Assume after some number of steps we have k 1’s. If the rightmost bitis a 0, we flip it to become a 1, which is the only operation we perform. Wealso add one token, which accounts for the additional 1 in the number. Ifthe rightmost r bits are 1’s, we flip them all to 0’s (costing r tokens) and thenext 0 to a 1 (gaining one token). So we spend r tokens and gained one, sowe have k − r + 1. But this is also the number of 1’s, because we startedwith k, performed r flips from 1 to 0 and one from 0 to 1.Taking these two together, we know the invariant that the number oftokens equals the number of 1s is true at the beginning and preserved byevery increment. It therefore must always be true.The total number of operations for n increments is the sum of the 0 → 1flips (which is n) and 1 → 0 flips. The latter is bounded by the number ofLECTURE NOTES SEPTEMBER 14, 2010Lists and Queues L7.4tokens, of which we put aside n over n operations. It is therefore O(n) andthe total number of bit flips is O(2 ∗ n) = O(n).3 Linked ListsLinked lists are a common alternative to arrays in the implementation ofdata structures. Each item in a linked list contains a data element of sometype and a pointer to the next item in the list. It is easy to insert and deleteelements in a linked lists, which is not a natural operation on arrays. Onthe other hand access to an element in the middle of the list is usually O(n),where n is the length of the list.An item in a linked list consists of a struct containing the data elementand a pointer to another linked list. This gives rise to the following defini-tion:struct list {string data;struct list* next;};typedef struct list* list;This definition is an example of a recursive type. A struct of this typecontains a pointer to another struct of the same type, and so on. We usu-ally use the special element of type t*, namely NULL, to indicate that wehave reached the end of the list. Sometimes (as will be the case for queuesintroduced next), we can avoid the explicit use of NULL and obtain more el-egant code. The type definition is there to create the type name list, whichstands for a pointer to a struct list.There are some restriction on recursive types. For example, a declara-tion such asstruct infinite {int x;struct infinite next;}would be rejected by the C0 compiler because it would require an infiniteamount of space. The general rule is that a struct can be recursive, butthe


View Full Document

CMU CS 15122 - Lecture Notes on Lists and Queues

Download Lecture Notes on Lists and Queues
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes on Lists and Queues and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes on Lists and Queues 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?