Anki Deck Changes

Note 1: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: M,?u9cw(S%

modified

Before

Front

{{c1:: \(\sum_{i = 1}^{n} i\log(i)\)}} \(\leq\) \(O(n \log(n))\) (Sum)

Back

{{c1:: \(\sum_{i = 1}^{n} i\log(i)\)}} \(\leq\) \(O(n \log(n))\) (Sum)

After

Front

{{c1:: \(\sum_{i = 1}^{n} i\log(i)\)}} \(\leq\) \(O(n \log(n))\) (O notation)

Back

{{c1:: \(\sum_{i = 1}^{n} i\log(i)\)}} \(\leq\) \(O(n \log(n))\) (O notation)

Field-by-field Comparison

Field	Before	After
Text	{{c1:: \(\sum_{i = 1}^{n} i\log(i)\)}}  \(\leq\) {{c2::\(O(n \log(n))\)}} (~~Sum~~)	{{c1:: \(\sum_{i = 1}^{n} i\log(i)\)}}  \(\leq\) {{c2::\(O(n \log(n))\)}} (O notation)

Tags: ETH::1._Semester::A&D::02._Asymptotic_Notation::3._O-Notation::Sums

Note 2: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: nzfDv_KLH2

modified

Before

Front

Runtime of Bubble Sort?

Back

Runtime of Bubble Sort?

Best Case: \(O(n)\)
Worst Case: \(O(n^2)\)
We use \(\Theta(n^2)\) comparisons and \(O(n^2)\) switches.

After

Front

Runtime of Bubble Sort?

Back

Runtime of Bubble Sort?

Best Case: \(O(n^2)\)
Worst Case: \(O(n^2)\)
We use \(\Theta(n^2)\) comparisons and \(O(n^2)\) switches.

Field-by-field Comparison

Field	Before	After
Runtime	Best Case: \(O(n)\)<br>Worst Case: \(O(n^2)\)	Best Case: \(O(n^2)\)<br>Worst Case: \(O(n^2)\)

Tags: ETH::1._Semester::A&D::04._Sorting_Algorithms::1._Bubble_Sort

Note 3: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: pOtqbJPwg.

modified

Before

Front

Runtime of Selection Sort?

Back

Runtime of Selection Sort?

Best Case: \(O(n^2)\)

Worst Case: \(O(n^2)\)

After

Front

Runtime of Selection Sort?

Back

Runtime of Selection Sort?

Best Case: \(O(n^2)\)

Worst Case: \(O(n^2)\)

Field-by-field Comparison

Field	Before	After
Pseudocode	<img src="paste-e41e8fe78828c54643b03175043cfb7610ff04df.jpg">	<img src="paste-e41e8fe78828c54643b03175043cfb7610ff04df.jpg"><div>(This has the sorted list at the start thus searches the smallest element)</div>

Tags: ETH::1._Semester::A&D::04._Sorting_Algorithms::2._Selection_Sort

Note 4: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: v,>nr{ym:e

added

Note did not exist

New Note

Front

What is an ADT?

Back

What is an ADT?

An abstract data type describes a wishlist for operations we want to perform on our data.

Field-by-field Comparison

Field	Before	After
Front		What is an ADT?
Back		An <b>abstract data type</b> describes a wishlist for operations we want to perform on our data.

Tags: ETH::1._Semester::A&D::05._Data_Structures

Note 5: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: xdGDHE`#zR

added

Note did not exist

New Note

Front

A datastructure is the implementation of the wishlist of operations defined in our ADT.

Back

A datastructure is the implementation of the wishlist of operations defined in our ADT.

Field-by-field Comparison

Field	Before	After
Text		A {{c1:: datastructure}} is the implementation of the wishlist of operations defined in our ADT.

Tags: ETH::1._Semester::A&D::05._Data_Structures

Note 6: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: F*Z7jn}vxk

added

Note did not exist

New Note

Front

The ADT List defines the following operations:

insert(k, L): insert the key K at the end of the list L
get(i, L): return the memory address of the i-th key in list L
delete(k, L): remove the key k from the list L
insertAfter(k, k', L): inserts the key k' after the key k in the list L

Back

The ADT List defines the following operations:

insert(k, L): insert the key K at the end of the list L
get(i, L): return the memory address of the i-th key in list L
delete(k, L): remove the key k from the list L
insertAfter(k, k', L): inserts the key k' after the key k in the list L

Field-by-field Comparison

Field	Before	After
Text		The ADT <b>List</b> defines the following operations:<br><ul><li>{{c1:: <b>insert(k, L)</b>}}: {{c2:: insert the key <b>K</b> at the end of the list <b>L</b>}}</li><li>{{c3:: <b>get(i, L)</b>}}: {{c4:: return the memory address of the i-th key in list <b>L</b> }}</li><li>{{c4:: <b>delete(k, L)</b>}}: {{c5:: remove the key <b>k</b> from the list <b>L</b>}}</li><li>{{c6::<b>insertAfter(k, k', L)</b>}}: {{c7:: inserts the key <b>k'</b> after the key <b>k</b> in the list <b>L</b>}}</li></ul>

Tags: ETH::1._Semester::A&D::05._Data_Structures::List

Note 7: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: ruU|XgSe,e

added

Note did not exist

New Note

Front

What extra pointer does the ADT List store?

Back

What extra pointer does the ADT List store?

It stores an extra pointer to the end of the list (in a LinkedList to the last node, in an array to delimit the last element).

Field-by-field Comparison

Field	Before	After
Front		What extra pointer does the ADT List store?
Back		It stores an extra pointer to the end of the list (in a LinkedList to the last node, in an array to delimit the last element).

Tags: ETH::1._Semester::A&D::05._Data_Structures::List

Note 8: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: s6a5!K0P)L

added

Note did not exist

New Note

Front

Operation	Array	Singly Linked List	Doubly Linked List
`insert(k,L)`	\(O(1)\)	\(O(1)\)	\(O(1)\)
`get(i,L)`	\(O(1)\)	\(O(l)\)	\(O(j)\)
`insertAfter(k,k',L)`	\(O(l)\)	\(O(1)\)	\(O(1)\)
`delete(k,L)`	\(O(l)\)	\(O(l)\)	\(O(1)\)
We assume to have a pointer to the end of the list here.

Back

Operation	Array	Singly Linked List	Doubly Linked List
`insert(k,L)`	\(O(1)\)	\(O(1)\)	\(O(1)\)
`get(i,L)`	\(O(1)\)	\(O(l)\)	\(O(j)\)
`insertAfter(k,k',L)`	\(O(l)\)	\(O(1)\)	\(O(1)\)
`delete(k,L)`	\(O(l)\)	\(O(l)\)	\(O(1)\)
We assume to have a pointer to the end of the list here.

Field-by-field Comparison

Field	Before	After
Text		<table> <tbody><tr> <th>Operation</th> <th>Array</th> <th>Singly Linked List</th> <th>Doubly Linked List</th> </tr> <tr> <td><code>insert(k,L)</code></td> <td>{{c1:: \(O(1)\)}}</td> <td>{{c2:: \(O(1)\)}}</td> <td>{{c3:: \(O(1)\)}}</td> </tr> <tr> <td><code>get(i,L)</code></td> <td>{{c4:: \(O(1)\)}}</td> <td>{{c5:: \(O(l)\)}}</td> <td>{{c6:: \(O(j)\)}}</td> </tr> <tr> <td><code>insertAfter(k,k',L)</code></td> <td>{{c7:: \(O(l)\)}}</td> <td>{{c8:: \(O(1)\)}}</td> <td>{{c9:: \(O(1)\)}}</td> </tr> <tr> <td><code>delete(k,L)</code></td> <td>{{c10:: \(O(l)\)}}</td> <td>{{c11:: \(O(l)\)}}</td> <td>{{c12:: \(O(1)\)}}</td> </tr> <tr> <td><em><br>We assume to have a pointer to the end of the list here.</em></td> <td></td> <td></td> <td></td> </tr></tbody></table>

Tags: ETH::1._Semester::A&D::05._Data_Structures::List

Note 9: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: qBT+Ifr6uX

added

Note did not exist

New Note

Front

In what situation is the array the correct datastructure?

Back

In what situation is the array the correct datastructure?

When we have a fixed upper bound for the size of the list.

Field-by-field Comparison

Field	Before	After
Front		In what situation is the array the correct datastructure?
Back		When we have a fixed upper bound for the size of the list.

Tags: ETH::1._Semester::A&D::05._Data_Structures::List::Array

Note 10: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: HNA(>OC%7u

added

Note did not exist

New Note

Front

In an array we can:

Insert in \(O(1)\) as we know the first empty cell in the array and can just write the key there
Get in \(O(1)\) as we know the offset for each key
InsertAfter in \(\Theta(l)\), since we have to shift the entire contents of the array behind the newly inserted element by 1.
Delete in \(\Theta(l)\) as in the worst case (Delete first element) we need to shift all to the left by 1.

Back

In an array we can:

Insert in \(O(1)\) as we know the first empty cell in the array and can just write the key there
Get in \(O(1)\) as we know the offset for each key
InsertAfter in \(\Theta(l)\), since we have to shift the entire contents of the array behind the newly inserted element by 1.
Delete in \(\Theta(l)\) as in the worst case (Delete first element) we need to shift all to the left by 1.

Field-by-field Comparison

Field	Before	After
Text		In an array we can:<br><ul><li><b>Insert</b> in {{c1:: \(O(1)\) as we know the first empty cell in the array and can just write the key there}}</li><li><b>Get</b> in {{c2::\(O(1)\) as we know the offset for each key}}</li><li><b>InsertAfter</b> in {{c3::\(\Theta(l)\), since we have to shift the entire contents of the array behind the newly inserted element by 1.}}<br></li><li><b>Delete</b> in {{c4::\(\Theta(l)\) as in the worst case (Delete first element) we need to shift all to the left by 1.}}<br></li></ul>

Tags: ETH::1._Semester::A&D::05._Data_Structures::List::Array

Note 11: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: rp1#iPsvnq

added

Note did not exist

New Note

Front

In a linked list, the keys don't appear in order in memory. They each contain {c2::a pointer to the start of the next element in the list instead}}.

We also have an extra pointer to the end in practice.

Back

The last pointer of the list is a null pointer to indicate the end.

Field-by-field Comparison

Field	Before	After
Text		In a <b>linked list</b>, the keys {{c1::don't appear in order in memory}}. They each contain {c2::a pointer to the start of the next element in the list instead}}.<br><br>We also have {{c3::an extra pointer to the end in practice}}.
Extra		The last pointer of the list is a null pointer to indicate the end.

Tags: ETH::1._Semester::A&D::05._Data_Structures::List::LL

Note 12: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: D!4=n6GM2_

added

Note did not exist

New Note

Front

In a doubly linked list, we store a pointer to the previous and next element for each key.

This increases memory usage as a trade-off for speed.

Back

In a doubly linked list, we store a pointer to the previous and next element for each key.

This increases memory usage as a trade-off for speed.

Field-by-field Comparison

Field	Before	After
Text		In a <b>doubly linked list</b>, we store a pointer to the {{c1:: previous and next element}} for each key.<br><br>This increases {{c2::memory usage}} as a trade-off for {{c2:: speed}}.

Tags: ETH::1._Semester::A&D::05._Data_Structures::List::LL

Note 13: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: Pf|C9|^n[w

added

Note did not exist

New Note

Front

In a singly and doubly linked list, the operation:

Insert is \(\Theta(1)\) as we know the memory address of the final element in the list and just have to set the null pointer to the new keys address. Without this pointer it's \(\Theta(l)\).
Get is \(\Theta(i)\) very slow as we need to traverse the entire list up to i
insertAfter is \(O(1)\) if we get the memory address of the element to insert after.
delete is:
SLL: {{c4::\(\Theta(l)\) as we need to find the previous element and change it's pointer.}
DLL: \(O(1)\) we know the address of the previous element and then just edit it's pointer.

Back

In a singly and doubly linked list, the operation:

Insert is \(\Theta(1)\) as we know the memory address of the final element in the list and just have to set the null pointer to the new keys address. Without this pointer it's \(\Theta(l)\).
Get is \(\Theta(i)\) very slow as we need to traverse the entire list up to i
insertAfter is \(O(1)\) if we get the memory address of the element to insert after.
delete is:
SLL: {{c4::\(\Theta(l)\) as we need to find the previous element and change it's pointer.}
DLL: \(O(1)\) we know the address of the previous element and then just edit it's pointer.

Field-by-field Comparison

Field	Before	After
Text		In a <b>singly</b> and <b>doubly linked list</b>, the operation:<br><ul><li><b>Insert</b> is {{c1::\(\Theta(1)\) as we know the memory address of the final element in the list and just have to set the null pointer to the new keys address. Without this pointer it's \(\Theta(l)\). }}<br></li><li><b>Get</b> is {{c2::\(\Theta(i)\) very slow as we need to traverse the entire list up to <b>i</b>}}<br></li><li><b>insertAfter</b> is {{c3:: \(O(1)\) if we get the memory address of the element to insert after.}}<br></li><li><b>delete</b> is:<br>      SLL: {{c4::\(\Theta(l)\) as we need to find the previous element and change it's pointer.}<br>      DLL: {{c5:: \(O(1)\) we know the address of the previous element and then just edit it's pointer.}}</li></ul>

Tags: ETH::1._Semester::A&D::05._Data_Structures::List::LL

Note 14: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: OGBoPi1aY*

added

Note did not exist

New Note

Front

The ADTs stack and queue behave similarly to a list, but with more constrained operations that allow more efficient computation.

Back

The ADTs stack and queue behave similarly to a list, but with more constrained operations that allow more efficient computation.

Field-by-field Comparison

Field	Before	After
Text		The ADTs {{c2::<b>stack</b> and <b>queue</b>}} behave similarly to a {{c1:: list}}, but  with {{c3:: more constrained operations that allow more efficient computation}}.

Tags: ETH::1._Semester::A&D::05._Data_Structures

Note 15: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: Ah6X9iA&#j

added

Note did not exist

New Note

Front

The ADT stack has the following operations:

push(k, S): push a new object k to the top of the stack S
pop(S): remove and return the top element of the stack S
top(S): get the top element of the stack S without deleting it

Back

The ADT stack has the following operations:

push(k, S): push a new object k to the top of the stack S
pop(S): remove and return the top element of the stack S
top(S): get the top element of the stack S without deleting it

Other operations might be isEmpty or emptystack which produces and emtpy stack.

Field-by-field Comparison

Field	Before	After
Text		The ADT <b>stack</b> has the following operations:<br><ul><li>{{c1:: <b>push(k, S)</b>}}: {{c2:: push a new object <b>k</b> to the top of the stack <b>S</b>}}</li><li>{{c3:: <b>pop(S)</b>}}: {{c4:: remove and return the top element of the stack <b>S</b>}}</li><li>{{c5:: <b>top(S)</b>}}: {{c6:: get the top element of the stack <b>S</b> without deleting it}}</li></ul>
Extra		Other operations might be <b>isEmpty</b> or <b>emptystack</b> which produces and emtpy stack.

Tags: ETH::1._Semester::A&D::05._Data_Structures::Stack

Note 16: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: nK{)v6I%zc

added

Note did not exist

New Note

Front

The ADT stack can be efficiently implemented using a singly linked list:

push: \(\Theta(1)\)
pop: \(\Theta(1)\) as this removes the first element. This means we just copy the pointer next from the first element to be the first pointer of the list.

Back

The ADT stack can be efficiently implemented using a singly linked list:

push: \(\Theta(1)\)
pop: \(\Theta(1)\) as this removes the first element. This means we just copy the pointer next from the first element to be the first pointer of the list.

Field-by-field Comparison

Field	Before	After
Text		The ADT <b>stack</b> can be efficiently implemented using a {{c1:: <b>singly linked list</b>}}:<br><ul><li><b>push</b>: {{c2:: \(\Theta(1)\)}}<br></li><li><b>pop</b>: {{c3:: \(\Theta(1)\) as this removes the first element. This means we just copy the pointer next from the first element to be the first pointer of the list.}}<br></li></ul>

Tags: ETH::1._Semester::A&D::05._Data_Structures::Stack

Note 17: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: u)lmsqp*H!

added

Note did not exist

New Note

Front

A stack is also called a LIFO queue.

Back

A stack is also called a LIFO queue.

Field-by-field Comparison

Field	Before	After
Text		A stack is also called a {{c1:: LIFO}} queue.

Tags: ETH::1._Semester::A&D::05._Data_Structures::Stack

Note 18: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: yy3TxuBe~r

added

Note did not exist

New Note

Front

A queue is also called FIFO.

Back

A queue is also called FIFO.

Field-by-field Comparison

Field	Before	After
Text		A queue is also called {{c1:: FIFO}}.

Tags: ETH::1._Semester::A&D::05._Data_Structures::Queue

Note 19: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID:

D2>~h


            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::1._Semester::A&D::05._Data_Structures::Queue
  
  
    The ADT quue has the following operations:
 enqueue(k, S):  append at the end of the queue
 dequeue(S):  remove and return the first element of the queue
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::A&D::05._Data_Structures::Queue
  
  
    The ADT quue has the following operations:
 enqueue(k, S):  append at the end of the queue
 dequeue(S):  remove and return the first element of the queue
    
    
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            The ADT&nbsp;<b>quue</b>&nbsp;has the following operations:<br><ul><li>{{c1::&nbsp;<b>enqueue(k, S)</b>}}: {{c2:: append at the end of the queue}}</li><li>{{c3::&nbsp;<b>dequeue(S)</b>}}: {{c4:: remove and return the first element of the queue}}</li></ul>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::1._Semester::A&D::05._Data_Structures::Queue

Field	Before	After
Text		The ADT <b>quue</b> has the following operations:<br><ul><li>{{c1:: <b>enqueue(k, S)</b>}}: {{c2:: append at the end of the queue}}</li><li>{{c3:: <b>dequeue(S)</b>}}: {{c4:: remove and return the first element of the queue}}</li></ul>


        
        
            Note 20: ETH::A&D
            
                Deck: ETH::A&D

                Note Type: Horvath Cloze

                GUID: F^&OZQURkx
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::1._Semester::A&D::05._Data_Structures::Queue
  
  
    The ADT queue can be efficiently implemented using a  singly linked list with a pointer to the end:
push:   \(O(1)\) insert at the end, with pointer to the end
pop:   \(O(1)\) remove the first element like in a stack
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::A&D::05._Data_Structures::Queue
  
  
    The ADT queue can be efficiently implemented using a  singly linked list with a pointer to the end:
push:   \(O(1)\) insert at the end, with pointer to the end
pop:   \(O(1)\) remove the first element like in a stack
    
    
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            The ADT&nbsp;<b>queue</b>&nbsp;can be efficiently implemented using a {{c1::&nbsp;<b>singly linked list with a pointer to the end</b>}}:<br><ul><li><b>push</b>: {{c2::&nbsp; \(O(1)\)&nbsp;insert at the end, with pointer to the end}}<br></li><li><b>pop</b>: {{c3::&nbsp; \(O(1)\)&nbsp;remove the first element like in a stack}}</li></ul>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::1._Semester::A&D::05._Data_Structures::Queue
                    
                
            
            
        
        
        
            Note 21: ETH::A&D
            
                Deck: ETH::A&D

                Note Type: Horvath Cloze

                GUID: s++QypVica
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::1._Semester::A&D::05._Data_Structures::Queue
  
  
    A PriorityQueue is like a queue, with the difference that  every key is associated with a natural number which indicates the importance.
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::A&D::05._Data_Structures::Queue
  
  
    A PriorityQueue is like a queue, with the difference that  every key is associated with a natural number which indicates the importance.
    
    
    
    The elements are then returned in the order of this importance.
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            A&nbsp;<b>PriorityQueue</b>&nbsp;is like a queue, with the difference that {{c1:: every key is associated with a natural number which indicates the importance}}.
                        
                        
                        
                            Extra
                            
                            The elements are then returned in the order of this importance.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::1._Semester::A&D::05._Data_Structures::Queue
                    
                
            
            
        
        
        
            Note 22: ETH::A&D
            
                Deck: ETH::A&D

                Note Type: Horvath Cloze

                GUID: Ld,vXkta~C
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::1._Semester::A&D::05._Data_Structures::Queue
  
  
    The ADT priorityQueue has the following operations:
 insert: insert with priority p
 extractMax: removes and returns element with highest priority.

  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::A&D::05._Data_Structures::Queue
  
  
    The ADT priorityQueue has the following operations:
 insert: insert with priority p
 extractMax: removes and returns element with highest priority.

    
    
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            The ADT <b>priorityQueue</b>&nbsp;has the following operations:<br><ul><li><b>{{c1:: insert}}</b>: {{c2::insert with priority&nbsp;<b>p}}</b><br></li><li><b>{{c3:: extractMax}}</b>: {{c4::removes and returns element with highest priority.}}<br></li></ul>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::1._Semester::A&D::05._Data_Structures::Queue
                    
                
            
            
        
        
        
            Note 23: ETH::A&D
            
                Deck: ETH::A&D

                Note Type: Horvath Cloze

                GUID: t/(N7FzdP}
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::1._Semester::A&D::05._Data_Structures::Queue
  
  
    The ADT priorityQueue can be efficiently implemented using a  MaxHeap. This guarantees  \(O(\log n)\) for both operations.
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::A&D::05._Data_Structures::Queue
  
  
    The ADT priorityQueue can be efficiently implemented using a  MaxHeap. This guarantees  \(O(\log n)\) for both operations.
    
    
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            <div>The ADT&nbsp;<b>priorityQueue</b>&nbsp;can be efficiently implemented using a {{c1::&nbsp;<b>MaxHeap</b>}}. This guarantees {{c2::&nbsp;\(O(\log n)\)}} for both operations.</div>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::1._Semester::A&D::05._Data_Structures::Queue
                    
                
            
            
        
        
        
            Note 24: ETH::DiskMat
            
                Deck: ETH::DiskMat

                Note Type: Horvath Cloze

                GUID: Mqpm#lUsGl
            
            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups::3._Inverses_and_Groups
  
  
    A function \(f: A \rightarrow A\) has a right inverse if and only if \(f\) is surjective.
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups::3._Inverses_and_Groups
  
  
    A function \(f: A \rightarrow A\) has a right inverse if and only if \(f\) is surjective.
    
    
  



                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups::3._Inverses_and_Groups
  
  
    A function \(f: A \rightarrow B\) has a right inverse if and only if \(f\) is surjective.
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups::3._Inverses_and_Groups
  
  
    A function \(f: A \rightarrow B\) has a right inverse if and only if \(f\) is surjective.
    
    
  



                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            <p>A function \(f: A \rightarrow A\) has a {{c1::right inverse}} if and only if \(f\) is {{c2::surjective}}.</p>
                            <p>A function \(f: A \rightarrow B\) has a {{c1::right inverse}} if and only if \(f\) is {{c2::surjective}}.</p>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups::3._Inverses_and_Groups
                    
                    
                    
                
            
            
        
        
        
            Note 25: ETH::DiskMat
            
                Deck: ETH::DiskMat

                Note Type: Horvath Cloze

                GUID: HM@g5s7n?R
            
            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups::3._Inverses_and_Groups
  
  
    A function \(f: A \rightarrow A\) has an inverse \(f^{-1}\) if and only if \(f\) is bijective.
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups::3._Inverses_and_Groups
  
  
    A function \(f: A \rightarrow A\) has an inverse \(f^{-1}\) if and only if \(f\) is bijective.
    
    
  



                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups::3._Inverses_and_Groups
  
  
    A function \(f: A \rightarrow B\) has an inverse \(f^{-1}\) if and only if \(f\) is bijective.
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups::3._Inverses_and_Groups
  
  
    A function \(f: A \rightarrow B\) has an inverse \(f^{-1}\) if and only if \(f\) is bijective.
    
    
  



                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            <p>A function \(f: A \rightarrow A\) has an {{c1::inverse}} \(f^{-1}\) if and only if \(f\) is {{c2::bijective}}.</p>
                            <p>A function \(f: A \rightarrow B\) has an {{c1::inverse}} \(f^{-1}\) if and only if \(f\) is {{c2::bijective}}.</p>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups::3._Inverses_and_Groups
                    
                    
                    
                
            
            
        
        
        
            Note 26: ETH::DiskMat
            
                Deck: ETH::DiskMat

                Note Type: Horvath Classic

                GUID: vx[#sC8q?V
            
            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::5._Algebra::8._Finite_Fields::3._Some_Facts_About_Finite_Fields_*
  
  
    What property does every finite field \(\text{GF}(q)\) have (and what does \(q\) satisfy)?
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::5._Algebra::8._Finite_Fields::3._Some_Facts_About_Finite_Fields_*
  
  
    What property does every finite field \(\text{GF}(q)\) have (and what does \(q\) satisfy)?
    
    Theorem 5.40: The multiplicative group of every finite field \(\text{GF}(q)\) is cyclic (as \(q\) is a power of a prime, if \(\text{GF}(q)\) is cyclic).
This group has order \(q - 1\) and \(\varphi(q-1)\) generators.
  






                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::5._Algebra::8._Finite_Fields::3._Some_Facts_About_Finite_Fields_*
  
  
    What property does every finite field \(\text{GF}(q)\) have (and what does \(q\) satisfy)?
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::5._Algebra::8._Finite_Fields::3._Some_Facts_About_Finite_Fields_*
  
  
    What property does every finite field \(\text{GF}(q)\) have (and what does \(q\) satisfy)?
    
    Theorem 5.40: The multiplicative group of every finite field \(\text{GF}(q)\) is cyclic (as \(q\) is a power of a prime, if \(\text{GF}(q)\) is cyclic).
This group has order \(q - 1\) and \(\varphi(q-1)\) generators.
Note that even though q is not prime thus not every integer is comprime, GF(q) is not Z_q.
  






                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Back
                            <p><strong>Theorem 5.40</strong>: The multiplicative group of every finite field \(\text{GF}(q)\) is cyclic (as \(q\) is a power of a prime, if \(\text{GF}(q)\) is cyclic).</p>
<p>This group has order \(q - 1\) and \(\varphi(q-1)\) generators.</p>
                            <p><strong>Theorem 5.40</strong>: The multiplicative group of every finite field \(\text{GF}(q)\) is cyclic (as \(q\) is a power of a prime, if \(\text{GF}(q)\) is cyclic).</p>
<p>This group has order \(q - 1\) and \(\varphi(q-1)\) generators.</p><p><i>Note that even though q is not prime thus not every integer is comprime, GF(q) is <b>not</b>&nbsp;Z_q.</i></p>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::1._Semester::DiskMat::5._Algebra::8._Finite_Fields::3._Some_Facts_About_Finite_Fields_*

Field	Before	After
Text		A <b>PriorityQueue</b> is like a queue, with the difference that {{c1:: every key is associated with a natural number which indicates the importance}}.
Extra		The elements are then returned in the order of this importance.