Our site saves small pieces of text information (cookies) on your device in order to deliver better content and for statistical purposes. You can disable the usage of cookies by changing the settings of your browser. By browsing our website without changing the browser settings you grant us permission to store that information on your device.

# Amortized

This is the task corresponding to exercise 4. Amortized.

## Resources

### Definitions File

```theory Defs
imports Main
begin

declare [[names_short]]
declare Let_def[simp]

(* Definitions *)
type_synonym 'a stk = "('a list * 'a list)"

definition empty :: "'a stk" where
"empty \<equiv> ([],[])"

fun push :: "'a \<Rightarrow> 'a stk \<Rightarrow> 'a stk" where
"push x (xs,ys) = (x#xs,ys)"

definition balance :: "'a list \<Rightarrow> 'a stk" where
"balance xs = (let n = length xs div 2 in (take n xs, rev (drop n xs)))"

fun pop_fst :: "'a stk \<Rightarrow> 'a stk" where
"pop_fst (x#xs,ys) = (xs,ys)"
| "pop_fst ([],ys) = balance (drop 1 (rev ys))"

fun pop_lst :: "'a stk \<Rightarrow> 'a stk" where
"pop_lst (xs,y#ys) = (xs,ys)"
| "pop_lst (xs,[]) = balance (butlast xs)"

(* Timings *)
definition T_push :: "'a \<Rightarrow> 'a stk \<Rightarrow> int" where
"T_push x stk = 1"

fun T_pop_fst :: "'a stk \<Rightarrow> int" where
"T_pop_fst (x#xs,ys) = 1"
| "T_pop_fst ([],ys) = int (length ys)"

fun T_pop_lst :: "'a stk \<Rightarrow> int" where
"T_pop_lst (xs,y#ys) = 1"
| "T_pop_lst (xs,[]) = int (length xs)"

consts \<Phi> :: "'a stk \<Rightarrow> int"

end```

### Template File

```theory Submission
imports Defs
begin

fun \<Phi> :: "'a stk \<Rightarrow> int" where
"\<Phi> _ = undefined"

lemma \<Phi>_ge_0: "\<Phi> (xs,ys) \<ge> 0"
sorry

lemma \<Phi>_empty_0: "\<Phi> empty = 0"
sorry

lemma T_push: "T_push x (xs,ys) + \<Phi> (push x (xs,ys)) - \<Phi> (xs,ys) \<le> c\<^sub>1"
oops

lemma T_pop_fst: "T_pop_fst (xs,ys) + \<Phi> (pop_fst (xs,ys)) - \<Phi> (xs,ys) \<le> c\<^sub>2"
oops

lemma T_pop_lst: "T_pop_lst (xs,ys) + \<Phi> (pop_lst (xs,ys)) - \<Phi> (xs,ys) \<le> c\<^sub>3"
oops

end```

### Check File

```theory Check
imports Submission
begin

lemma \<Phi>_ge_0: "\<Phi> (xs,ys) \<ge> 0"
by (rule Submission.\<Phi>_ge_0)

lemma \<Phi>_empty_0: "\<Phi> empty = 0"
by (rule Submission.\<Phi>_empty_0)

end```

Terms and Conditions